前端
2023 年 8 月 28 日
TS的数据结构使用实战(树)
本系列文章会从实践的角度去讲解一些常用的数据结构在ts中的应用实例,因为要保证数据结构的通用性,把数据结构和数据本身的类型分离开,所以就会用到ts的泛型。 本文讲的是树在ts中的实战。
树的种类又很多,以下是维基百科中给出的树的种类:
其实树的种类不止这些,但是核心的数据结构是相同的,区别只是树的维护、操作方法不同,在实际应用中,树的维护和操作方法会因树的类型和要求而异,以满足特定的需求和性能要求。
我们选用相对简单的二叉树来演示如何在 TS 中实现。
二叉树的类式实现
二叉树的数据存储有点像我们前面讲过的链表,本身只存储根元素(root)的信息,在通过节点之间的关系去操作数据。
interface BinaryTreeNode<T> {
value: T;
left: BinaryTreeNode<T> | null;
right: BinaryTreeNode<T> | null;
}
class BinaryTree<T> {
private root: BinaryTreeNode<T> | null;
constructor() {
this.root = null;
}
add(value: T) {
const newNode: BinaryTreeNode<T> = {
value: value,
left: null,
right: null,
};
if (!this.root) {
this.root = newNode;
} else {
this.addNode(this.root, newNode);
}
}
private addNode(node: BinaryTreeNode<T>, newNode: BinaryTreeNode<T>) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.addNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.addNode(node.right, newNode);
}
}
}
// 其他二叉树的操作方法
// ...
}
通过使用泛型接口
TreeNode<T>
和泛型类 Tree<T>
,我们可以构建一个通用的树数据结构。泛型约束可以确保树节点的值为特定类型,避免不正确的操作。二叉树的函数式实现
函数式实现也是类似的方式,将树的根节点存储在闭包中,并返回树的操作方法供使用。
type BinaryTreeNode<T> = {
value: T;
left: BinaryTreeNode<T> | null;
right: BinaryTreeNode<T> | null;
};
type BinaryTree<T> = {
add: (value: T) => void;
// 其他二叉树的操作方法
// ...
};
function newBinaryTree<T>(): BinaryTree<T> {
let root: BinaryTreeNode<T> | null = null;
function add(value: T) {
const newNode: BinaryTreeNode<T> = {
value: value,
left: null,
right: null,
};
if (!root) {
root = newNode;
} else {
addNode(root, newNode);
}
}
function addNode(node: BinaryTreeNode<T>, newNode: BinaryTreeNode<T>) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
addNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
addNode(node.right, newNode);
}
}
}
return {
add,
// 其他二叉树的操作方法
// ...
};
}
这样,一个简单二叉树的函数式实现(工厂函数)就完成了。
本系列暂时完结★,°:.☆( ̄ ▽  ̄)/$:.°★ 。
版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
作者: LunaSeki 发表日期:2023 年 8 月 28 日