二叉树（Binary tree）是由一组表示层次树结构的链接节点组成的数据结构。每个节点通过父子关系链接到其他节点。任何给定节点最多可以有两个子节点（左和右）。二叉树中的第一个节点是根，而没有任何子节点的节点是叶。
JavaScript 二叉树可视化
二叉树数据结构中的每个节点都必须具有以下属性：
-
key：节点的键 -
value：节点的值 -
parent：节点的父节点（如果没有，则为null） -
left：指向节点左子级的指针（如果没有，则为null） -
right：指向节点右子级的指针（如果没有，则为null）
二叉树数据结构的主要操作有：
-
insert：将节点作为给定父节点的子节点插入 -
remove：从二叉树中删除节点及其子节点 -
find: 检索给定节点 -
preOrderTraversal：通过递归遍历每个节点及其子节点来遍历二叉树 -
postOrderTraversal：通过递归遍历每个节点的子节点，然后遍历该节点，从而遍历二叉树 -
inOrderTraversal：通过递归遍历每个节点的左子级，然后是该节点，然后是其右子级来遍历二叉树
JavaScript 实现
class BinaryTreeNode {
constructor(key, value = key, parent = null) {
this.key = key
this.value = value
this.parent = parent
this.left = null
this.right = null
}
get isLeaf() {
return this.left === null && this.right === null
}
get hasChildren() {
return !this.isLeaf
}
}
class BinaryTree {
constructor(key, value = key) {
this.root = new BinaryTreeNode(key, value)
}
*inOrderTraversal(node = this.root) {
if (node.left) yield* this.inOrderTraversal(node.left)
yield node
if (node.right) yield* this.inOrderTraversal(node.right)
}
*postOrderTraversal(node = this.root) {
if (node.left) yield* this.postOrderTraversal(node.left)
if (node.right) yield* this.postOrderTraversal(node.right)
yield node
}
*preOrderTraversal(node = this.root) {
yield node
if (node.left) yield* this.preOrderTraversal(node.left)
if (node.right) yield* this.preOrderTraversal(node.right)
}
insert(parentNodeKey, key, value = key, { left, right } = { left: true, right: true }) {
for (const node of this.preOrderTraversal()) {
if (node.key === parentNodeKey) {
const canInsertLeft = left && node.left === null
const canInsertRight = right && node.right === null
if (!canInsertLeft && !canInsertRight) return false
if (canInsertLeft) {
node.left = new BinaryTreeNode(key, value, node)
return true
}
if (canInsertRight) {
node.right = new BinaryTreeNode(key, value, node)
return true
}
}
}
return false
}
remove(key) {
for (const node of this.preOrderTraversal()) {
if (node.left.key === key) {
node.left = null
return true
}
if (node.right.key === key) {
node.right = null
return true
}
}
return false
}
find(key) {
for (const node of this.preOrderTraversal()) {
if (node.key === key) return node
}
return undefined
}
}
- 创建一个具有
constructor的BinaryTreeNode类（class），为每个实例初始化key、value、parent、left和right属性。 - 定义一个
isLeafgetter，使用Array.prototype.length检查left和right是否为空。 - 定义一个
hasChildrengetter，它与isLeafgetter 相反。 - 创建一个具有
constructor的BinaryTree类（class），初始化二叉树的root。 - 定义一个
preOrderTraversal()按预先顺序遍历二叉树生成器方法，使用yield*语法递归地将遍历委托给自身。 - 定义一个
postOrderTraversal()以后序遍历二叉树的生成器方法，使用yield*语法递归地将遍历委托给自身， - 定义一个
inOrderTraversal()按顺序遍历二叉树的生成器方法，使用yield*语法递归地将遍历委托给自身。 - 定义一个
insert()方法，使用preOrderTraversal()方法查找给定的父节点，并根据传递的选项对象插入一个新的子BinaryTreeNode作为left或right子节点。 - 定义一个
remove()方法，使用preOrderTraversal()方法和Array.prototype.filter()从二叉树中删除二进制树节点。 - 定义一个
find()方法，使用preOrderTraversal()方法检索二叉树中的给定节点。
const tree = new BinaryTree(1, 'AB')
tree.insert(1, 11, 'AC')
tree.insert(1, 12, 'BC')
tree.insert(12, 121, 'BG', { right: true })
;[...tree.preOrderTraversal()].map(x => x.value) // ['AB', 'AC', 'BC', 'BCG']
;[...tree.inOrderTraversal()].map(x => x.value) // ['AC', 'AB', 'BC', 'BG']
tree.root.value // 'AB'
tree.root.hasChildren // true
tree.find(12).isLeaf // false
tree.find(121).isLeaf // true
tree.find(121).parent.value // 'BC'
tree.find(12).left // null
tree.find(12).right.value // 'BG'
tree.remove(12)
;[...tree.postOrderTraversal()].map(x => x.value) // ['AC', 'AB']
以上内容译自 30 seconds of code 的 JavaScript Data Structures - Binary Tree
网友评论