樹結(jié)構(gòu)
- 樹(Tree)： n(n>=0)個節(jié)點構(gòu)成的有限集合。
- 當 n = 0時，稱為空樹
- 對于任一課非空樹(n>0)，它具備以下性質(zhì)：
- 樹中有一個成為“根（root)”的特殊節(jié)點，用 r標識
- 其余節(jié)點分為m(m>0)個互不相交的有限集T1，T2,T3....Tm, 其中每個集合本身又是一顆樹，稱為原來樹的“子樹（SubTree）”
樹的術(shù)語
- 節(jié)點的度： 節(jié)點的子樹個數(shù)（比如二叉樹一個節(jié)點只有兩個分支，度為2. 最下面的節(jié)點，沒有分支了，度為0）。
- 樹的度： 樹的所有節(jié)點中最大的度數(shù) （如果某個節(jié)點有4個分支，其他節(jié)點都沒這么多，那么樹的度為4）。
- 葉節(jié)點： 度為0的節(jié)點
- 父節(jié)點：有子樹的節(jié)點
- 子節(jié)點：若A節(jié)點是B節(jié)點的父節(jié)點，則稱B節(jié)點是A節(jié)點的子節(jié)點
- 兄弟節(jié)點： 具有同一父節(jié)點的節(jié)點彼此稱為兄弟節(jié)點
- 路徑和路徑長度： 從節(jié)點n1到nk的路徑稱為一個節(jié)點的序列n1,n2,n3....nk， ni是ni+1的父節(jié)點。 路徑說包含
邊的個數(shù)為路徑的長度。（從跟節(jié)點沿著分支一直走到底，沒有其他分支了。這個就是路徑。路徑中每個節(jié)點連接的分支就是邊 ） - 節(jié)點的層次： 規(guī)定根節(jié)點在1層， 其他任一節(jié)點的層數(shù)是其父節(jié)點的層數(shù)加1
- 樹的深度： 所有節(jié)點的最大層級是這個樹的深度。
二叉樹
二叉樹（binary tree）是指樹中節(jié)點的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節(jié)點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹 [2] 。
特殊類型
- 滿二叉樹：如果一棵二叉樹只有度為0的結(jié)點和度為2的結(jié)點，并且度為0的結(jié)點在同一層上，則這棵二叉樹為滿二叉樹 。
- 完全二叉樹：深度為k，有n個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應時，稱為完全二叉樹
任何一棵樹都可以轉(zhuǎn)換為二叉樹
image.png
二叉樹的存儲
- 數(shù)組（2n-1找到左邊的節(jié)點， 2n+2找右邊的節(jié)點）
image.png
-
鏈表(使用鏈表更合適)
image.png
二叉搜索樹
二叉搜索樹(Binary Search Tree),（又：二叉查找樹，二叉排序樹）
- 二叉搜索樹是一顆二叉樹，可以為空
- 如果不為空，滿足以下性質(zhì)：
- 非空左子樹的所有鍵值小于根節(jié)點的鍵值
- 非空右子樹的所有鍵值大于根節(jié)點的鍵值
- 左、右子樹本身也是二叉搜索樹
特點：
- 二叉搜索樹的特點是 較小的值 總是保存在左節(jié)點上， 較大的值總是保存在右節(jié)點上
樹的遍歷
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結(jié)點的系統(tǒng)的訪問，即依次對樹中每個結(jié)點訪問一次且僅訪問一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。 （先訪問父節(jié)點(從根節(jié)點開始）就叫前序， 中間訪問父節(jié)點叫做中序， 最后訪問父節(jié)點叫做后序）
js 實現(xiàn)代碼
// 創(chuàng)建BinarySearchTree
function BinarySerachTree() {
// 創(chuàng)建節(jié)點構(gòu)造函數(shù)
function Node(key) {
this.key = key
this.left = null
this.right = null
}
// 保存根的屬性
this.root = null
// 二叉搜索樹相關(guān)的操作方法
// 向樹中插入數(shù)據(jù)
BinarySerachTree.prototype.insert = function (key) {
// 1.根據(jù)key創(chuàng)建對應的node
var newNode = new Node(key)
// 2.判斷根節(jié)點是否有值，沒有直接賦值
if (this.root === null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
BinarySerachTree.prototype.insertNode = function (node, newNode) {
// 1.準備向左子樹插入數(shù)據(jù) 插入的值比當前節(jié)點的值小，往左節(jié)點插入
if (newNode.key < node.key) {
if (node.left === null) { // 1.1.node的左子樹上沒有內(nèi)容
node.left = newNode
} else {
// 1.2.node的左子樹上已經(jīng)有了內(nèi)容 遞歸調(diào)用，直到插入到正確的位置
this.insertNode(node.left, newNode)
}
} else { // 2.準備向右子樹插入數(shù)據(jù)
if (node.right === null) { // 2.1.node的右子樹上沒有內(nèi)容
node.right = newNode
} else { // 2.2.node的右子樹上有內(nèi)容
this.insertNode(node.right, newNode)
}
}
}
// 獲取最大值和最小值
// 最小值，最左邊的節(jié)點值
BinarySerachTree.prototype.min = function () {
var node = this.root
while (node.left !== null) {
node = node.left
}
return node.key
}
// 最大值 最右邊的節(jié)點值
BinarySerachTree.prototype.max = function () {
var node = this.root
while (node.right !== null) {
node = node.right
}
return node.key
}
// 搜搜特定的值
/*
BinarySerachTree.prototype.search = function (key) {
return this.searchNode(this.root, key)
}
BinarySerachTree.prototype.searchNode = function (node, key) {
// 1.如果傳入的node為null那么, 那么就退出遞歸
if (node === null) {
return false
}
// 2.判斷node節(jié)點的值和傳入的key大小
if (node.key > key) { // 2.1.傳入的key較小, 向左邊繼續(xù)查找
return this.searchNode(node.left, key)
} else if (node.key < key) { // 2.2.傳入的key較大, 向右邊繼續(xù)查找
return this.searchNode(node.right, key)
} else { // 2.3.相同, 說明找到了key
return true
}
}
*/
// 查找值 存不存在
BinarySerachTree.prototype.search = function (key) {
var node = this.root
while (node !== null) {
if (node.key > key) {
node = node.left
} else if (node.key < key) {
node = node.right
} else {
// 找到 返回 true
return true
}
}
// 其他情況 返回 false
return false
}
BinarySerachTree.prototype.removeNode = function (node, key) {
// 1.如果傳入的node為null, 直接退出遞歸.
if (node === null) return null
// 2.判斷key和對應node.key的大小
if (node.key > key) {
node.left = this.removeNode(node.left, key)
}
}
// 刪除結(jié)點
BinarySerachTree.prototype.remove = function (key) {
// 1.定義臨時保存的變量
var current = this.root
// 當前節(jié)點的父節(jié)點 初始根節(jié)點無父節(jié)點
var parent = null
// 標識 判斷是否是 左節(jié)點
var isLeftChild = true
// 2.開始查找節(jié)點
while (current.key !== key) {
// 再查找子節(jié)點前，先把當前節(jié)點保存到parent中。 就是之后節(jié)點的父節(jié)點
parent = current
// 如果 需要刪除的值小于 當前節(jié)點值
if (key < current.key) {
// 設置 標識 isLeftChild 為true
// 并 把當前節(jié)點設置為 左節(jié)點
isLeftChild = true
current = current.left
} else {
isLeftChild = false
current = current.right
}
// 如果發(fā)現(xiàn)current已經(jīng)指向null, 那么說明沒有找到要刪除的數(shù)據(jù)
if (current === null) return false
}
// 到這里沒有 return 說名找到了節(jié)點
// 3.刪除的結(jié)點是葉結(jié)點 該 節(jié)點 沒有 子節(jié)點 最簡單
if (current.left === null && current.right === null) {
// 如果當前節(jié)點就是根節(jié)點，并且沒有子節(jié)點 。直接把根節(jié)點 置為 null 即可
if (current == this.root) {
this.root == null
} else if (isLeftChild) {
// 如果 這是 左節(jié)點 ，那把當前節(jié)點的父節(jié)點 的 left置為null
parent.left = null
} else {
parent.right = null
}
}
// 4.刪除有一個子節(jié)點的節(jié)點 （上面已經(jīng)排除了 左右節(jié)點同時 不存在的情況）
// 只有 判斷 一個節(jié)點不存在的情況，另一個節(jié)點肯定存在
else if (current.right === null) {
// 如果當前節(jié)點是根節(jié)點，右節(jié)點不存在。 那么直接把左節(jié)點賦值給 根節(jié)點
// 根節(jié)點就被刪除了。 原來根節(jié)點的左節(jié)點作為 現(xiàn)在的根節(jié)點
if (current == this.root) {
this.root = current.left
} else if (isLeftChild) {
// 如果需要刪除的節(jié)點 是左節(jié)點，并且不存在右子節(jié)點的情況，
// 把刪除節(jié)點的左節(jié)點賦值為 父節(jié)點的左節(jié)點即可
parent.left = current.left
} else {
parent.right = current.left
}
} else if (current.left === null) {
if (current == this.root) {
this.root = current.right
} else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
}
// 5.刪除有兩個節(jié)點的節(jié)點
// 存在兩個節(jié)點的情況 比較復雜。 要么采用前驅(qū)找到左邊的最大節(jié)點（都小于右邊的節(jié)點值），要么才有后繼找到右邊的最小節(jié)點(都大于左邊的節(jié)點值)
// 替換掉需要刪除的節(jié)點
else {
// 1.獲取后繼節(jié)點 （這里用后繼方式）
// getSuccessor獲取的后繼節(jié)點 以及處理好了右子節(jié)點
var successor = this.getSuccessor(current)
// 2.判斷是否是根節(jié)點
// 如果需要刪除的是根節(jié)點，那么直接把右邊找到的最小節(jié)點賦值給root即可
if (current == this.root) {
this.root = successor
} else if (isLeftChild) {
// 如果需要刪除的節(jié)點是左節(jié)點
// 把刪除節(jié)點的父節(jié)點 的left 改為 后繼節(jié)點
parent.left = successor
} else {
parent.right = successor
}
// 上面只是 把后繼節(jié)點接上 了父節(jié)點
// 還需要把刪除節(jié)點的左子節(jié)點 拼接到 后繼節(jié)點上的左節(jié)點上
// 3.將刪除節(jié)點的左子樹賦值給successor
successor.left = current.left
}
return true
}
// 前驅(qū)，是小于x.key的最大關(guān)鍵字的結(jié)點。(獲取需要刪除節(jié)點，左邊節(jié)點里面最大的節(jié)點值| 左邊節(jié)點，一直往右)
// 后繼，是大于x.key的最小關(guān)鍵字的結(jié)點 （獲取需要刪除節(jié)點，右邊節(jié)點里面的最小的節(jié)點值 | 右邊節(jié)點一直往左）
// 找后繼的方法
BinarySerachTree.prototype.getSuccessor = function (delNode) {
// 1.使用變量保存臨時的節(jié)點
// 保存 后繼節(jié)點的父節(jié)點
var successorParent = delNode
// 保存找到的后繼 默認為刪除節(jié)點
var successor = delNode
// 要從右子樹開始找
var current = delNode.right
// 2.尋找節(jié)點
// current 為 null 的情況下 就找到了
// 一直往昨早
while (current != null) {
successorParent = successor
successor = current
current = current.left
}
// 1. 如果后繼節(jié)點 不是 刪除節(jié)點的右節(jié)點（即 刪除的節(jié)點不是 剛好是只有一個右節(jié)點）
// 需要把刪除節(jié)點的 由節(jié)點 賦值到 后繼節(jié)點的右節(jié)點
// 2. 后繼節(jié)點 雖然沒有左節(jié)點了。但是存在 右節(jié)點的情況。
// 需要把 后繼節(jié)點的右節(jié)點 賦值給 后繼節(jié)點父節(jié)點的左節(jié)點
// 然后再把 刪除節(jié)點的右節(jié)點賦值給后繼節(jié)點的 右節(jié)點
// 返回 getSuccessor 之后 會把后繼節(jié)點移動到 刪除節(jié)點的位置
if (successor != delNode.right) {
successorParent.left = successorParent.right
successor.right = delNode.right
}
}
// 遍歷方法
// 先序遍歷 (先執(zhí)行handler函數(shù))
BinarySerachTree.prototype.preOrderTraversal = function (handler) {
this.preOrderTranversalNode(this.root, handler)
}
BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
if (node !== null) {
// 先執(zhí)行 handler函數(shù)
handler(node.key)
// 一直遞歸調(diào)用查找左節(jié)點，直到?jīng)]有左節(jié)點后，返回上一層，再執(zhí)行右節(jié)點
// 右節(jié)點里面又遞歸，找左節(jié)點。。。。
this.preOrderTranversalNode(node.left, handler)
this.preOrderTranversalNode(node.right, handler)
}
}
// 中序遍歷（再找到最左邊的節(jié)點后再執(zhí)行handler函數(shù)）
BinarySerachTree.prototype.inOrderTraversal = function (handler) {
this.inOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
if (node !== null) {
this.inOrderTraversalNode(node.left, handler)
handler(node.key)
this.inOrderTraversalNode(node.right, handler)
}
}
// 后續(xù)遍歷
BinarySerachTree.prototype.postOrderTraversal = function (handler) {
this.postOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
if (node !== null) {
this.postOrderTraversalNode(node.left, handler)
this.postOrderTraversalNode(node.right, handler)
handler(node.key)
}
}
}
// 測試代碼
var bst = new BinarySerachTree()
// 插入數(shù)據(jù)
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
// // 測試前序遍歷結(jié)果
// var resultString = ""
// bst.preOrderTraversal(function (key) {
// resultString += key + " "
// })
// alert(resultString) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
//
// // 測試中序遍歷結(jié)果
// resultString = ""
// bst.inOrderTraversal(function (key) {
// resultString += key + " "
// })
// alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//
// // 測試后續(xù)遍歷結(jié)果
// resultString = ""
// bst.postOrderTraversal(function (key) {
// resultString += key + " "
// })
// alert(resultString) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
//
// // 獲取最值
// alert(bst.min()) // 3
// alert(bst.max()) // 25
//
// // 查找特定的值
// alert(bst.search(10)) // true
// alert(bst.search(21)) // false
// 查找數(shù)據(jù)
alert(bst.remove(10))
alert(bst.remove(20))
alert(bst.remove(21))
缺點：
不平衡二叉樹： 如果按順序插入節(jié)點，比如 9，8，7，6，5，4，3，1. 這樣二叉樹就類似于鏈表了。如果輸入序列已經(jīng)排序，則時間復雜度為O(N)
平衡二叉樹/紅黑樹就是為了將查找的時間復雜度保證在O(logN)范圍內(nèi)
