二叉树的定义
二叉树是一种数据结构,它由一组称为节点的元素组成,这些节点通过边连接。每个节点最多可以有两个子节点,分别称为左子节点和右子节点。
二叉树的主要方法有:
- 创建
- 添加节点
- 查找节点
- 删除节点
- 获得树的高度
- 获得树的节点树
- 各种遍历方法(请参考我的博客里对于二叉树的前序、中序、后续遍历描述的文章)
二叉树的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class Node { constructor(data) { this.parent = null this.data = data this.left = null this.right = null } }
class Tree { constructor() { this.root = null this.size = 0 } insert(data) {}
remove(data) { } size() { } minNode() { } maxNode() { } height() {} }
|
插入节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class Tree { constructor() { this.root = null this.size = 0 }
insert(data) { const newNode = new Node(data) if (!this.root) { this.root = newNode } else { this.insertNode(this.root, newNode) } }
insertNode(node, newNode) { if (newNode.data < node.data) { if (!node.left) { node.left = newNode newNode.parent = node } else { this.insertNode(node.left, newNode) } } else { if (!node.right) { node.right = newNode newNode.parent = node } else { this.insertNode(node.right, newNode) } } } }
|
查找节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Tree {
find(data) { return this.find(this.root,data) }
findNode(node,data) { if (!node) { return null } if (data == node.data) { return node } else if (data < node.data) { return this.findNode(node.left, data) } else { return this.findNode(node.right, data) } } }
|
删除节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| remove(data) { let node = this.find(data) if (node) { this.size-- if (node === this.root) { this.root = null return true } let left = node.left,right = node.right let parent = node.parent let isLeft = parent && parent.left === node if (!left && !right) { if (isLeft) { parent.left = null } else { parent.right = null } } else if (left && !right) { if (isLeft) { parent.left = left } else { parent.right = left } left.parent = parent } else if (!left && right) { if (isLeft) { parent.left = right } else { parent.right = right } right.parent = parent } else if (left && right) { let child = right while (child.left) { child = child.left } this.remove(child.data) node.data = child.data } } }
|
删除二叉树的节点比较复杂,主要有4种情况,这里解释一下每种情况的处理方法:
- 被删除的节点是叶子节点,直接删除即可。判断它是父节点的哪一边的孩子节点,将相应的属性设置为null。
- 被删除的节点只有左子节点,需要用它的左子节点把它自己给替换下去。
- 被删除的节点只有右子节点,需要用它的右子节点把它自己给替换下去。
- 被删除的节点有左右2个子节点。这时候我们需要考虑是用左子树继位还是用右子树继位。如果用左子树继位(实例代码中使用右子树继位),需要找到左子树最靠右的节点。如果该节点没有子节点,只需用它替换目标节点。如果该节点有一个左子节点,请将其替换为左子节点,然后将目标节点替换为最右边的节点。
删除节点的第四种情况最为复杂,一般书中给出的操作方式读起来非常的费劲。上面的解释来自书籍《算法基础》,但是具体操作的时候有一些技巧。在使用左子树继位的时候,找到了最右边的节点值,把它的值记录下来,然后删除这个节点,最后把原先要删除的值与记录的值替换。这样就相当于完成了上面的节点替换的操作(操作来自《JavaScript算法》)。
最大值与最小值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| minNode(node) { var cur = node || this.root while (cur.left) { cur = cur.left } return cur } maxNode() { var cur = this.root while (cur.right) { cur = cur.right } return cur } getMax() { var node = this.maxNode() return node ? node.data : null } getMin() { var node = this.minNode() return node ? node.data : null }
|
高度
1 2 3 4 5 6 7 8 9 10 11
| height() { return this.getNodeHeight(this.root) } getNodeHeight(node) { if (node == null) { return 0 } let leftChildHeight = this.getNodeHeight(node.left) let rightChildHeight = this.getNodeHeight(node.right) return Math.max(leftChildHeight, rightChildHeight) + 1 }
|
节点数量
1 2 3 4 5 6 7 8 9 10 11
| size() { return this.size } getNodeSize(node) { if (node == null) { return 0 } let leftChildSize = this.getNodeSize(node.left) let rightChildSize = this.getNodeSize(node.right) return leftChildSize + rightChildSize + 1 }
|
翻转二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| invertTree() { if (root === null) { return null; }
let temp = root.left; root.left = root.right; root.right = temp;
this.invertTree(root.left); this.invertTree(root.right);
return root }
|