class Node {
constructor (data, left, right) {
this.data = data
this.left = left
this.right = right
}
}
class Tree {
constructor () {
this.root = null
}
insert(data) {
const newNode = new Node(data, null, null)
if (!this.root) {
this.root = newNode
} else {
let cur = this.root
while(1) {
if (cur.data < data) {
if (!cur.right) {
cur.right = newNode
break
}
cur = cur.right
} else {
if (!cur.left) {
cur.left = newNode
break
}
cur = cur.left
}
}
}
}
// 中序遍历
inOrder (node) {
if (node != null) {
this.inOrder(node.left)
console.log(node.data)
this.inOrder(node.right)
}
}
// 前序遍历
preOrder (node) {
if (node != null) {
console.log(node.data)
this.preOrder(node.left)
this.preOrder(node.right)
}
}
// 后序遍历
nextOrder (node) {
if (node != null) {
this.nextOrder(node.left)
this.nextOrder(node.right)
console.log(node.data)
}
}
// 广度遍历
guangdu() {
const queue = []
const pushChild = (node) => {
if (node.left) {
queue.unshift(node.left)
}
if (node.right) {
queue.unshift(node.right)
}
}
queue.push(this.root)
while(queue.length) {
const c = queue.pop()
console.log(c.data)
pushChild(c)
}
}
// 深度遍历
shendu() {
const queue = []
const pushChild = (node) => {
if (node.left) {
queue.push(node.left)
}
if (node.right) {
queue.push(node.right)
}
}
queue.push(this.root)
while(queue.length) {
const c = queue.pop()
console.log(c.data)
pushChild(c)
}
}
// 取得最小值
getMin (node) {
node = node ? node : this.root
if (!node.left) {
return node
} else {
return this.getMin(node.left)
}
}
// 取得最大值
getMax (node) {
node = node ? node : this.root
if (!node.right) {
return node
} else {
return this.getMax(node.right)
}
}
// 查找节点
find (data) {
let cur = this.root
while (cur) {
if (data < cur.data) {
cur = cur.left
} else if (data > cur.data) {
cur = cur.right
} else {
return cur
}
}
}
// 移除节点
remove (node, data) {
if (node === null) {
return null
}
if (data < node.data) {
node.left = this.remove(node.left, data)
return node
} else if (data > node.data) {
node.right = this.remove(node.right, data)
return node
} else {
if (node.left === null && node.right === null) {
return null
}
else if (node.left === null) {
return node.right
}
else if (node.right === null) {
return node.left
}
else {
// 右子树的最左节点
// const _node = this.getMin(node.right)
// node.data = _node.data
// node.right = this.remove(node.right, node.data)
// 左子树的最右节点
const _node = this.getMax(node.left)
node.data = _node.data
node.left = this.remove(node.left, node.data)
return node
}
}
}
}
const tree = new Tree()
tree.insert(2)
tree.insert(1)
tree.insert(8)
tree.insert(4)
tree.insert(6)
tree.insert(3)
tree.insert(2)
tree.insert(9)
tree.insert(5)
tree.insert(7)
tree.insert(10)
tree.remove(tree.root, 8)
console.log(tree)
// tree.nextOrder(tree.root)
// console.log(tree.getMin())
// console.log(tree.getMax())
// console.log(tree.find(3))
同样的一串数字，插入的先后顺序不同，那么形成的二叉树排列也不同
说一下删除节点，被删除节点如果两个子树都存在：
- 选取左子树的最右节点的值替换掉被删除节点的值
- 删除左子树的最右节点
同理，用右子树的最左节点去做上面两步也是可以的
为什么要左子树的最右节点呢？
因为要选取一个其它节点换到被删除节点的位置，这个节点要比被删除节点的左子树的根节点要大，比右子树的根节点要小，那么可以从左子树的右子树中选择，这个右子树中有很多节点啊，选谁都可以，但是为了方便起见，我们取一个最大值，即是左子树中的最右节点，因为末端节点可能只有一个子树或者没有子树，删除最右节点时，将子树的值替换到最右节点的位置即可。
删除节点后树的排列方式只有一种吗？
不是
- 按照上面两种利用左子树的最右节点或者右子树的最左节点，最少是两种方式
- 上面说了，为了方便起见，我们使用了左子树的最右节点，如果不考虑方便，有很多节点都可以考虑，排列方式又是不一样的
1.jpg
遍历：
前序遍历：根-左-右
中序遍历：左-根-右
后续遍历：左-右-根
看出规律了吧！
还有这种遍历顺序不仅仅是针对整个二叉树，其实也针对每个局部的子树
类似动态规划，将大问题拆解成小问题，从整体看局部
22.jpg
拿中序遍历举例：
23.jpg
可以看出，这个步骤是可以通过递归来完成的
我们先去递归左子树，然后直接输出根元素，然后再去递归右子树
对于左子树，重复上述过程
对于左子树的左子树，重复上述过程
...
同理，对于右子树也是上述过程
可能，同学们对于上述遍历的递归写法还是有点不太理解，那么分析一下：
// 中序遍历
inOrder (node) {
if (node != null) {
this.inOrder(node.left)
console.log(node.data)
this.inOrder(node.right)
}
}
意思是：如果节点不为 null，那么先去递归左子树，输出根节点值，递归右子树
左边递归不走完的话，console.log 是永远不会执行的
递归有递归的终止条件，不然就会无限递归，这个条件就是 node == null
那么左递归停止，就代表上一次递归的子树没有左节点，直接输出子树的根节点
然后开始递归该子树的右子树，同理，对于右子树的每一个节点，也是先开始递归左子树，输出根节点值，递归右子树
所以，对于一棵树中的所有节点，都要走这个递归的3个过程。一个节点完全递归完毕，就是左子树递归完毕，输出根节点值，右子树递归完毕。即递归到叶子节点的时候，因为叶子节点没有左子树，也没有右子树，最终输出该叶子节点的值。
24.jpg
网友评论