树形数据结构用途广泛，了解其基本工作原理很有帮助。树是其他常用数据结构（例如 Map 和 Set）的基础。此外，数据库也使用树形数据结构来实现快速搜索。HTML DOM 也使用树形数据结构来表示元素的层次结构。本文将探讨不同类型的树，例如二叉树、二叉搜索树以及它们的实现方法。
在上一篇文章中，我们探讨了图数据结构，它是树的推广形式。现在让我们开始学习什么是树数据结构吧！
您可以在Github代码库中找到所有这些实现以及更多内容：
amejiarosario / dsa.js-数据结构-算法-javascript
这是DSA.js 书籍的代码实现以及 NPM 包的仓库。
在这个代码库中，你可以找到 JavaScript 中算法和数据结构的实现。这些资料可以作为开发者的参考手册，也可以帮助你在面试前复习特定主题。此外，你还可以从中获得更高效的问题解决方法。
您可以克隆此仓库或从 NPM 安装代码：
npm install dsa.js
然后您可以将其导入到您的程序或命令行界面中。
const { LinkedList, Queue, Stack } = require('dsa.js');
有关所有可用数据结构和算法的列表，请参阅 index.js。
算法至关重要……
树是一种数据结构，其中每个节点可以有零个或多个子节点。每个节点都包含一个值。与图类似，节点之间的连接称为边。树是图的一种类型，但并非所有图都是树（稍后会详细介绍）。
这些数据结构被称为“树”，因为这种数据结构类似于树🌳。它从根节点开始，分支出后代节点，最后是叶子节点。
以下是树木的一些特性：
A高度为 3I高度为 0H深度为 2B深度为 1正如我们之前看到的，树节点只是一个具有值并与其后代节点链接的数据结构。
以下是一个树节点的示例：
class TreeNode {
constructor(value) {
this.value = value;
this.descendents = [];
}
}
我们可以创建一个包含 3 个后代的树，如下所示：
// create nodes with values
const abe = new TreeNode('Abe');
const homer = new TreeNode('Homer');
const bart = new TreeNode('Bart');
const lisa = new TreeNode('Lisa');
const maggie = new TreeNode('Maggie');
// associate root with is descendents
abe.descendents.push(homer);
homer.descendents.push(bart, lisa, maggie);
就这样，我们得到了一个树状数据结构！
节点abe是树的根节点，而节点bart、节点lisa和maggie节点是树的叶节点。请注意，树的节点可以有不同数量的后代节点：0、1、3 或任何其他值。
树形数据结构有很多应用，例如：
树的节点可以有零个或多个子节点。但是，当一棵树最多只有两个子节点时，它就被称为二叉树。
根据二叉树中节点的排列方式，它可以是满二叉树、完全二叉树和完美二叉树：
请看以下示例：
这些属性并非总是互斥的。您可以同时拥有多个属性：
2^k - 1\个节点，其中k是树的最后一层（从 1 开始）。full。
二叉搜索树（简称 BST）是二叉树的一种特殊应用。与所有二叉树一样，BST 最多只有两个节点。然而，BST 的节点值必须满足以下条件：左子节点的值必须小于父节点的值，右子节点的值必须大于父节点的值。
重复项：有些二叉搜索树不允许重复元素，而有些则允许将相同的值添加到右子节点。其他实现可能会对重复元素的数量进行计数（我们稍后会讨论这一点）。
让我们来实现二叉搜索树吧！
二叉搜索树与我们之前实现的树非常相似。但是，两者之间也存在一些差异：
left < parent < right。这是树节点。它和我们之前做的非常相似，但我们为左右子节点添加了一些方便的 getter 和 setter 方法。请注意，它还保留了对父节点的引用，并且每次添加子节点时都会更新它。
const LEFT = 0;
const RIGHT = 1;
class TreeNode {
constructor(value) {
this.value = value;
this.descendents = [];
this.parent = null;
}
get left() {
return this.descendents[LEFT];
}
set left(node) {
this.descendents[LEFT] = node;
if (node) {
node.parent = this;
}
}
get right() {
return this.descendents[RIGHT];
}
set right(node) {
this.descendents[RIGHT] = node;
if (node) {
node.parent = this;
}
}
}
好的，目前我们已经可以添加左子节点和右子节点了。现在，让我们来编写强制执行该left < parent < right规则的二叉搜索树类。
class BinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
add(value) { /* ... */ }
find(value) { /* ... */ }
remove(value) { /* ... */ }
getMax() { /* ... */ }
getMin() { /* ... */ }
}
让我们来实现插入操作。
要在二叉树中插入节点，我们执行以下操作：
我们来举例说明如何插入 30、40、10、15、12、50：
我们可以按如下方式实现插入操作：
add(value) {
const newNode = new TreeNode(value);
if (this.root) {
const { found, parent } = this.findNodeAndParent(value);
if (found) { // duplicated: value already exist on the tree
found.meta.multiplicity = (found.meta.multiplicity || 1) + 1;
} else if (value < parent.value) {
parent.left = newNode;
} else {
parent.right = newNode;
}
} else {
this.root = newNode;
}
this.size += 1;
return newNode;
}
我们使用了一个名为 `counter` 的辅助函数findNodeAndParent。如果发现节点已存在于树中，则增加multiplicity计数器。让我们看看这个函数是如何实现的：
findNodeAndParent(value) {
let node = this.root;
let parent;
while (node) {
if (node.value === value) {
break;
}
parent = node;
node = ( value >= node.value) ? node.right : node.left;
}
return { found: node, parent };
}
findNodeAndParent遍历树查找该值。它从根节点（第 2 行）开始，然后根据该值向左或向右移动（第 10 行）。如果该值已存在，它将返回该节点found及其父节点。如果该节点不存在，我们仍然返回该值parent。
我们已经知道如何插入和查找值。现在，我们将实现删除操作。删除操作比添加操作稍微复杂一些，所以让我们通过以下示例来解释：
删除一个叶节点（0 个子节点）
30 30
/ \ remove(12) / \
10 40 ---------> 10 40
\ / \ \ / \
15 35 50 15 35 50
/
12*
我们只需将节点父节点（15）的引用删除为 null。
删除只有一个子节点的节点。
30 30
/ \ remove(10) / \
10* 40 ---------> 15 40
\ / \ / \
15 35 50 35 50
在这种情况下，我们找到父节点（30），并将子节点（10）替换为子节点的子节点（15）。
删除具有两个子节点的节点
30 30
/ \ remove(40) / \
15 40* ---------> 15 50
/ \ /
35 50 35
我们要移除节点 40，它有两个子节点（35 和 50）。我们将父节点（30）的子节点（40）替换为该子节点的右子节点（50）。然后，我们将左子节点（35）保留在原来的位置，因此我们需要将其设为 50 的左子节点。
另一种删除节点 40 的方法是，将左子节点 (35) 向上移动，然后保持右子节点 (50) 的位置不变。
30
/ \
15 35
\
50
两种方法都可以，只要保持二叉搜索树的性质即可：left < parent < right。
删除根目录。
30* 50
/ \ remove(30) / \
15 50 ---------> 15 35
/
35
删除根节点与我们之前讨论的删除拥有 0 个、1 个或 2 个子节点的节点非常相似。唯一的区别在于，删除根节点后，我们需要更新树根节点的引用。
以下是我们讨论内容的动画演示。
在动画中，它向上移动左侧子树，并保持右侧子树不变。
既然我们已经大致了解了它的运作方式，那就让我们来实施它吧：
remove(value) {
const nodeToRemove = this.find(value);
if (!nodeToRemove) return false;
// Combine left and right children into one subtree without nodeToRemove
const nodeToRemoveChildren = this.combineLeftIntoRightSubtree(nodeToRemove);
if (nodeToRemove.meta.multiplicity && nodeToRemove.meta.multiplicity > 1) {
nodeToRemove.meta.multiplicity -= 1; // handle duplicated
} else if (nodeToRemove === this.root) {
// Replace (root) node to delete with the combined subtree.
this.root = nodeToRemoveChildren;
this.root.parent = null; // clearing up old parent
} else {
const side = nodeToRemove.isParentLeftChild ? 'left' : 'right';
const { parent } = nodeToRemove; // get parent
// Replace node to delete with the combined subtree.
parent[side] = nodeToRemoveChildren;
}
this.size -= 1;
return true;
}
以下是实施过程中的一些亮点：
将左子树合并成右子树的函数如下：
二叉搜索树.prototype.combineLeftIntoRightSubtree
combineLeftIntoRightSubtree(node) {
if (node.right) {
const leftmost = this.getLeftmost(node.right);
leftmost.left = node.left;
return node.right;
}
return node.left;
}
例如，假设我们要合并以下树，并且即将删除节点 30。30我们希望将节点 30 的左子树合并到右子树中。结果如下：
30* 40
/ \ / \
10 40 combine(30) 35 50
\ / \ -----------> /
15 35 50 10
\
15
现在，如果我们把新的子树作为根节点，那么节点30就不存在了！
根据访问节点的顺序，遍历二叉树有多种方法：中序遍历、前序遍历和后序遍历。此外，我们还可以使用在图论文章中学到的深度优先搜索（DFS）和广度优先搜索（BFS） 。让我们逐一了解这些方法。
按顺序遍历
按顺序遍历访问节点的顺序为：左节点、父节点、右节点。
二叉搜索树.prototype.inOrderTraversal
* inOrderTraversal(node = this.root) {
if (node.left) { yield* this.inOrderTraversal(node.left); }
yield node;
if (node.right) { yield* this.inOrderTraversal(node.right); }
}
让我们用这棵树来举例：
10
/ \
5 30
/ / \
4 15 40
/
3
中序遍历会输出以下值：3, 4, 5, 10, 15, 30, 40。如果树是二叉搜索树，则节点将按升序排列，就像我们的示例中那样。
后序遍历
后序遍历按以下顺序访问节点：左节点、右节点、父节点。
二叉搜索树.prototype.postOrderTraversal
* postOrderTraversal(node = this.root) {
if (node.left) { yield* this.postOrderTraversal(node.left); }
if (node.right) { yield* this.postOrderTraversal(node.right); }
yield node;
}
后序遍历将输出以下值：3, 4, 5, 15, 40, 30, 10。
前序遍历和深度优先搜索
中序遍历按以下顺序访问节点：父节点、左节点、右节点
。BinarySearchTree.prototype.preOrderTraversal
* preOrderTraversal(node = this.root) {
yield node;
if (node.left) { yield* this.preOrderTraversal(node.left); }
if (node.right) { yield* this.preOrderTraversal(node.right); }
}
前序遍历会输出以下值：10, 5, 4, 3, 30, 15, 40。这种数字顺序与运行深度优先搜索（DFS）得到的结果相同。
* dfs() {
const stack = new Stack();
stack.add(this.root);
while (!stack.isEmpty()) {
const node = stack.remove();
yield node;
// reverse array, so left gets removed before right
node.descendents.reverse().forEach(child => stack.add(child));
}
}
如果您需要复习一下深度优先搜索（DFS），我们在Graph 文章中进行了详细介绍。
广度优先搜索（BFS）
与深度优先搜索（DFS）类似，我们可以通过切换参数来实现广度优先搜索（BFS Stack）Queue：
* bfs() {
const queue = new Queue();
queue.add(this.root);
while (!queue.isEmpty()) {
const node = queue.remove();
yield node;
node.descendents.forEach(child => queue.add(child));
}
}
广度优先搜索顺序为：10, 5, 30, 4, 15, 40, 3
到目前为止，我们已经讨论了如何操作add以及remove元素find。但是，我们还没有讨论运行时间。让我们考虑一下最坏的情况。
假设我们要按升序将数字相加。
最终所有节点都会集中在左侧！这棵不平衡树和链表没什么区别，所以查找元素的时间复杂度是O(n)。😱
在不平衡的树状图中查找信息，就像一页一页地翻字典查找单词一样。而当树状图平衡时，你可以从中间翻开字典，然后根据字母顺序和你要查找的单词，判断应该向左还是向右查找。
我们需要找到平衡这棵树的方法！
如果树是平衡的，那么我们可以用O(log n)的时间复杂度找到元素，而无需遍历每个节点。我们来谈谈什么是平衡树。
7如果在非平衡树中查找元素，我们需要从 1 到 7 遍历。然而，在平衡树中，我们只需要访问： 4，，6和7。树越大，情况就越糟糕。如果有一百万个节点，查找一个不存在的元素可能需要访问所有一百万个节点，而在平衡树中只需要访问 20 次！这差别太大了！
我们将在下一篇文章中使用自平衡树（AVL树）来解决这个问题。
我们已经讨论了很多内容。让我们用要点总结一下：