树 - 数据结构训练营

我们将要介绍的其余两种数据结构都属于树。 就像现实生活一样,有许多不同类型的树数据结构。 二叉树: - AA树、AVL树、二叉搜索树、二叉树、笛卡尔树、左孩子/右兄弟树、order statistic 树、Pagoda... B 树: - B 树、B+ 树、B* 树、B Sharp 树、Dancing 树、2-3 树、... 堆: - 堆、二叉堆、Weak 堆、Binomial 堆、斐波那契堆、莱昂纳多堆、2-3 堆、Soft 堆、Pairing 堆、Leftist 堆、Treap... 树: - Trie、Radix 树、Suffix 树、Suffix 数组、FM-index、B-trie... 多路树: - 三叉树、K 叉树、与或树、(a,b) 树、Link/Cut 树... 空间分区树: - Segment 树、Interval 树、Range 树、Bin、Kd 树、四叉树、八叉树、Z 阶、UB 树、R 树、X 树、度量树、覆盖树... 特定于应用程序的树: - 抽象语法树、解析树、决策树、极大极小树... 没想到吧,今天和树杠上了……而且这还没有列出全部的树。别怕,其中大部分树的只会出现在是科学家的论文里,而实际编程却用不到。 树很像图或链表,只是它们是“单向的”。这意味着它们不能有引用循环。 链表的基本思想类似于图,具有指向其他结点的结点,看起来像这样: 如果可以在树中的连接节点之间绘制一个循环......好吧,这不是树。 树有许多不同的用途,可用于优化搜索或排序,可以更好地组织程序,可以更好的描述数据。 我们将从一个非常简单的树结构开始。它没有任何特殊规则,看起来像这样: Tree { root: { value: 1, children: [{ value: 2, children: [...] }, { value: 3, children: [...] }] } } 实现树数据结构可以提供以下一些运算: 一个生成空树的构造函数; 遍历树中所有的元素; 给树添加结点; 下面我们将依次介绍其实现。 一个生成空树的构造函数 树必须从根节点开始,即树的根。 constructor() { this.root = null; } 遍历树中所有的元素 我们需要一个方法来遍历树并在树中的每个节点上调用一个回调函数。 traverse(callback) { // 定义一个可以在每个结点上递归调用的 walk 函数 function walk(node) { // 首先调用结点上的回调。 // 然后递归调用其所有子项的 walk 函数。 } // 现在开始遍历 walk(this.root); } 给树添加结点 接下来,我们需要一个向树添加结点的方法。 add(value, parentValue) { let newNode = { value, children: [] }; // 如果没有 root,只需将其设置为新结点即可。 // 否则遍历整个树并找到具有匹配值的结点并将新结点添加到其子结点。 } 这是最基本的树之一,并且可能仅在表示的数据实际上类似于树时才会用到。 但是通过一些额外的规则,树可以用于许多不同的目的。
使用正确的数据结构可以大大简化原本复杂的逻辑。如果很注重性能或想节约内存,那么就需要选择正确的数据结构。来和我一起用 JavaScript 语言来实现一些常用数据结构吧。


运行