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)
}
}
// 查找節(jié)點(diǎn)
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
}
}
}
// 移除節(jié)點(diǎn)
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 {
// 右子樹的最左節(jié)點(diǎn)
// const _node = this.getMin(node.right)
// node.data = _node.data
// node.right = this.remove(node.right, node.data)
// 左子樹的最右節(jié)點(diǎn)
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))
同樣的一串?dāng)?shù)字，插入的先后順序不同，那么形成的二叉樹排列也不同
說一下刪除節(jié)點(diǎn)，被刪除節(jié)點(diǎn)如果兩個(gè)子樹都存在：
- 選取左子樹的最右節(jié)點(diǎn)的值替換掉被刪除節(jié)點(diǎn)的值
- 刪除左子樹的最右節(jié)點(diǎn)
同理，用右子樹的最左節(jié)點(diǎn)去做上面兩步也是可以的
為什么要左子樹的最右節(jié)點(diǎn)呢？
因?yàn)橐x取一個(gè)其它節(jié)點(diǎn)換到被刪除節(jié)點(diǎn)的位置，這個(gè)節(jié)點(diǎn)要比被刪除節(jié)點(diǎn)的左子樹的根節(jié)點(diǎn)要大，比右子樹的根節(jié)點(diǎn)要小，那么可以從左子樹的右子樹中選擇，這個(gè)右子樹中有很多節(jié)點(diǎn)啊，選誰都可以，但是為了方便起見，我們?nèi)∫粋€(gè)最大值，即是左子樹中的最右節(jié)點(diǎn)，因?yàn)槟┒斯?jié)點(diǎn)可能只有一個(gè)子樹或者沒有子樹，刪除最右節(jié)點(diǎn)時(shí)，將子樹的值替換到最右節(jié)點(diǎn)的位置即可。
刪除節(jié)點(diǎn)后樹的排列方式只有一種嗎？
不是
- 按照上面兩種利用左子樹的最右節(jié)點(diǎn)或者右子樹的最左節(jié)點(diǎn)，最少是兩種方式
- 上面說了，為了方便起見，我們使用了左子樹的最右節(jié)點(diǎn)，如果不考慮方便，有很多節(jié)點(diǎn)都可以考慮，排列方式又是不一樣的
遍歷：
前序遍歷：根-左-右
中序遍歷：左-根-右
后續(xù)遍歷：左-右-根
看出規(guī)律了吧！
還有這種遍歷順序不僅僅是針對整個(gè)二叉樹，其實(shí)也針對每個(gè)局部的子樹
類似動(dòng)態(tài)規(guī)劃，將大問題拆解成小問題，從整體看局部
拿中序遍歷舉例：
可以看出，這個(gè)步驟是可以通過遞歸來完成的
我們先去遞歸左子樹，然后直接輸出根元素，然后再去遞歸右子樹
對于左子樹，重復(fù)上述過程
對于左子樹的左子樹，重復(fù)上述過程
...
同理，對于右子樹也是上述過程
可能，同學(xué)們對于上述遍歷的遞歸寫法還是有點(diǎn)不太理解，那么分析一下：
// 中序遍歷
inOrder (node) {
if (node != null) {
this.inOrder(node.left)
console.log(node.data)
this.inOrder(node.right)
}
}
意思是：如果節(jié)點(diǎn)不為 null，那么先去遞歸左子樹，輸出根節(jié)點(diǎn)值，遞歸右子樹
左邊遞歸不走完的話，console.log 是永遠(yuǎn)不會執(zhí)行的
遞歸有遞歸的終止條件，不然就會無限遞歸，這個(gè)條件就是 node == null
那么左遞歸停止，就代表上一次遞歸的子樹沒有左節(jié)點(diǎn)，直接輸出子樹的根節(jié)點(diǎn)
然后開始遞歸該子樹的右子樹，同理，對于右子樹的每一個(gè)節(jié)點(diǎn)，也是先開始遞歸左子樹，輸出根節(jié)點(diǎn)值，遞歸右子樹
所以，對于一棵樹中的所有節(jié)點(diǎn)，都要走這個(gè)遞歸的3個(gè)過程。一個(gè)節(jié)點(diǎn)完全遞歸完畢，就是左子樹遞歸完畢，輸出根節(jié)點(diǎn)值，右子樹遞歸完畢。即遞歸到葉子節(jié)點(diǎn)的時(shí)候，因?yàn)槿~子節(jié)點(diǎn)沒有左子樹，也沒有右子樹，最終輸出該葉子節(jié)點(diǎn)的值。
