節(jié)點(diǎn)： 樹中的每個元素稱為一個節(jié)點(diǎn)，
根節(jié)點(diǎn)： 位于整棵樹頂點(diǎn)的節(jié)點(diǎn)，它沒有父節(jié)點(diǎn)， 如上圖 5
子節(jié)點(diǎn)： 其他節(jié)點(diǎn)的后代
葉子節(jié)點(diǎn): 沒有子節(jié)點(diǎn)的元素稱為葉子節(jié)點(diǎn)， 如上圖 3 8 24
二叉樹：二叉樹就是一種數(shù)據(jù)結(jié)構(gòu)， 它的組織關(guān)系就像是自然界中的樹一樣。官方語言的定義是：是一個有限元素的集合,該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。
二叉查找樹：
二叉查找樹也叫二叉搜索樹（BST）,它只允許我們在左節(jié)點(diǎn)存儲比父節(jié)點(diǎn)更小的值，右節(jié)點(diǎn)存儲比父節(jié)點(diǎn)更大的值，上圖展示的就是一顆二叉查找樹。
首先創(chuàng)建一個類來表示二叉查找樹，它的內(nèi)部應(yīng)該有一個Node類，用來創(chuàng)建節(jié)點(diǎn)
function BinarySearchTree () {
var Node = function(key) {
this.key = key,
this.left = null,
this.right = null
}
var root = null
}它還應(yīng)該有一些方法：
insert(key) 插入一個新的鍵
inOrderTraverse() 對樹進(jìn)行中序遍歷，并打印結(jié)果
preOrderTraverse() 對樹進(jìn)行先序遍歷，并打印結(jié)果
postOrderTraverse() 對樹進(jìn)行后序遍歷，并打印結(jié)果
search(key) 查找樹中的鍵，如果存在返回true,不存在返回fasle
findMin() 返回樹中的最小值
findMax() 返回樹中的最大值
remove(key) 刪除樹中的某個鍵
向樹中插入一個新的鍵，首頁應(yīng)該創(chuàng)建一個用來表示新節(jié)點(diǎn)的Node類實(shí)例，因此需要new一下Node類并傳入需要插入的key值，它會自動初始化為左右節(jié)點(diǎn)為null的一個新節(jié)點(diǎn)
然后，需要做一些判斷，先判斷樹是否為空，若為空，新插入的節(jié)點(diǎn)就作為根節(jié)點(diǎn)，如不為空，調(diào)用一個輔助方法insertNode()方法，將根節(jié)點(diǎn)和新節(jié)點(diǎn)傳入
this.insert = function(key) {
var newNode = new Node(key)
if(root === null) {
root = newNode
} else {
insertNode(root, newNode)
}
}定義一下insertNode() 方法，這個方法會通過遞歸得調(diào)用自身，來找到新添加節(jié)點(diǎn)的合適位置
var insertNode = function(node, newNode) {
if (newNode.key <= node.key) {
if (node.left === null) {
node.left = newNode
}else {
insertNode(node.left, newNode)
}
}else {
if (node.right === null) {
node.right = newNode
}else {
insertNode(node.right, newNode)
}
}
}要實(shí)現(xiàn)中序遍歷，我們需要一個inOrderTraverseNode(node)方法，它可以遞歸調(diào)用自身來遍歷每個節(jié)點(diǎn)
this.inOrderTraverse = function() {
inOrderTraverseNode(root)
}這個方法會打印每個節(jié)點(diǎn)的key值，它需要一個遞歸終止條件————檢查傳入的node是否為null，如果不為空，就繼續(xù)遞歸調(diào)用自身檢查node的left、right節(jié)點(diǎn)
實(shí)現(xiàn)起來也很簡單:
var inOrderTraverseNode = function(node) {
if (node !== null) {
inOrderTraverseNode(node.left)
console.log(node.key)
inOrderTraverseNode(node.right)
}
}有了中序遍歷的方法，只需要稍作改動，就可以實(shí)現(xiàn)先序遍歷和后序遍歷了
上代碼：
這樣就可以對整棵樹進(jìn)行中序遍歷了
// 實(shí)現(xiàn)先序遍歷
this.preOrderTraverse = function() {
preOrderTraverseNode(root)
}
var preOrderTraverseNode = function(node) {
if (node !== null) {
console.log(node.key)
preOrderTraverseNode(node.left)
preOrderTraverseNode(node.right)
}
}
// 實(shí)現(xiàn)后序遍歷
this.postOrderTraverse = function() {
postOrderTraverseNode(root)
}
var postOrderTraverseNode = function(node) {
if (node !== null) {
postOrderTraverseNode(node.left)
postOrderTraverseNode(node.right)
console.log(node.key)
}
}發(fā)現(xiàn)了吧，其實(shí)就是內(nèi)部語句更換了前后位置，這也剛好符合三種遍歷規(guī)則：先序遍歷（根-左-右）、中序遍歷（左-根-右）、中序遍歷（左-右-根）
現(xiàn)在的完整代碼如下：
function BinarySearchTree () {
var Node = function(key) {
this.key = key,
this.left = null,
this.right = null
}
var root = null
//插入節(jié)點(diǎn)
this.insert = function(key) {
var newNode = new Node(key)
if(root === null) {
root = newNode
} else {
insertNode(root, newNode)
}
}
var insertNode = function(node, newNode) {
if (newNode.key <= node.key) {
if (node.left === null) {
node.left = newNode
}else {
insertNode(node.left, newNode)
}
}else {
if (node.right === null) {
node.right = newNode
}else {
insertNode(node.right, newNode)
}
}
}
//實(shí)現(xiàn)中序遍歷
this.inOrderTraverse = function() {
inOrderTraverseNode(root)
}
var inOrderTraverseNode = function(node) {
if (node !== null) {
inOrderTraverseNode(node.left)
console.log(node.key)
inOrderTraverseNode(node.right)
}
}
// 實(shí)現(xiàn)先序遍歷
this.preOrderTraverse = function() {
preOrderTraverseNode(root)
}
var preOrderTraverseNode = function(node) {
if (node !== null) {
console.log(node.key)
preOrderTraverseNode(node.left)
preOrderTraverseNode(node.right)
}
}
// 實(shí)現(xiàn)后序遍歷
this.postOrderTraverse = function() {
postOrderTraverseNode(root)
}
var postOrderTraverseNode = function(node) {
if (node !== null) {
postOrderTraverseNode(node.left)
postOrderTraverseNode(node.right)
console.log(node.key)
}
}
}竟然已經(jīng)完成了添加新節(jié)點(diǎn)和遍歷的方式，我們來測試一下吧：
定義一個數(shù)組，里面有一些元素
var arr = [9,6,3,8,12,15]
我們將arr中的每個元素依此插入到二叉搜索樹中，然后打印結(jié)果
var tree = new BinarySearchTree()
arr.map(item => {
tree.insert(item)
})
tree.inOrderTraverse()
tree.preOrderTraverse()
tree.postOrderTraverse()運(yùn)行代碼后，我們先來看看插入節(jié)點(diǎn)后整顆樹的情況：
輸出結(jié)果
中序遍歷：
3
6
8
9
12
15
先序遍歷：
9
6
3
8
12
15
后序遍歷：
3
8
6
15
12
9
很明顯，結(jié)果是符合預(yù)期的，所以，我們用上面的JavaScript代碼，實(shí)現(xiàn)了對樹的節(jié)點(diǎn)插入，和三種遍歷方法，同時，很明顯可以看到，在二叉查找樹樹種，最左側(cè)的節(jié)點(diǎn)的值是最小的，而最右側(cè)的節(jié)點(diǎn)的值是最大的，所以二叉查找樹可以很方便的拿到其中的最大值和最小值
怎么做呢？其實(shí)只需要將根節(jié)點(diǎn)傳入minNode/或maxNode方法，然后通過循環(huán)判斷node為左側(cè)(minNode)/右側(cè)(maxNode)的節(jié)點(diǎn)為null
實(shí)現(xiàn)代碼：
// 查找最小值
this.findMin = function() {
return minNode(root)
}
var minNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}
// 查找最大值
this.findMax = function() {
return maxNode(root)
}
var maxNode = function (node) {
if(node) {
while (node && node.right !== null) {
node =node.right
}
return node.key
}
return null
}this.search = function(key) {
return searchNode(root, key)
}同樣，實(shí)現(xiàn)它需要定義一個輔助方法,這個方法首先會檢驗(yàn)node的合法性，如果為null，直接退出，并返回fasle。如果傳入的key比當(dāng)前傳入node的key值小，它會繼續(xù)遞歸查找node的左側(cè)節(jié)點(diǎn)，反之，查找右側(cè)節(jié)點(diǎn)。如果找到相等節(jié)點(diǎn)，直接退出，并返回true
var searchNode = function(node, key) {
if (node === null) {
return false
}
if (key < node.key) {
return searchNode(node.left, key)
}else if (key > node.key) {
return searchNode(node.right, key)
}else {
return true
}
}移除節(jié)點(diǎn)的實(shí)現(xiàn)情況比較復(fù)雜，它會有三種不同的情況：
需要移除的節(jié)點(diǎn)是一個葉子節(jié)點(diǎn)
需要移除的節(jié)點(diǎn)包含一個子節(jié)點(diǎn)
需要移除的節(jié)點(diǎn)包含兩個子節(jié)點(diǎn)
和實(shí)現(xiàn)搜索指定節(jié)點(diǎn)一元，要移除某個節(jié)點(diǎn)，必須先找到它所在的位置，因此移除方法的實(shí)現(xiàn)中部分代碼和上面相同：
// 移除節(jié)點(diǎn)
this.remove = function(key) {
removeNode(root,key)
}
var removeNode = function(node, key) {
if (node === null) {
return null
}
if (key < node.key) {
node.left = removeNode(node.left, key)
return node
}else if(key > node.key) {
node.right = removeNode(node.right,key)
return node
}else{
//需要移除的節(jié)點(diǎn)是一個葉子節(jié)點(diǎn)
if (node.left === null && node.right === null) {
node = null
return node
}
//需要移除的節(jié)點(diǎn)包含一個子節(jié)點(diǎn)
if (node.letf === null) {
node = node.right
return node
}else if (node.right === null) {
node = node.left
return node
}
//需要移除的節(jié)點(diǎn)包含兩個子節(jié)點(diǎn)
var aux = findMinNode(node.right)
node.key = aux.key
node.right = removeNode(node.right, axu.key)
return node
}
}
var findMinNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node
}
return null
}其中，移除包含兩個子節(jié)點(diǎn)的節(jié)點(diǎn)是最復(fù)雜的情況，它包含左側(cè)節(jié)點(diǎn)和右側(cè)節(jié)點(diǎn)，對它進(jìn)行移除主要需要三個步驟：
需要找到它右側(cè)子樹中的最小節(jié)點(diǎn)來代替它的位置
將它右側(cè)子樹中的最小節(jié)點(diǎn)移除
將更新后的節(jié)點(diǎn)的引用指向原節(jié)點(diǎn)的父節(jié)點(diǎn)
有點(diǎn)繞兒，但必須這樣，因?yàn)閯h除元素后的二叉搜索樹必須保持它的排序性質(zhì)
tree.remove(8) tree.inOrderTraverse()
打印結(jié)果：
3
6
9
12
15
8 這個節(jié)點(diǎn)被成功刪除了，但是對二叉查找樹進(jìn)行中序遍歷依然是保持排序性質(zhì)的
到這里，一個簡單的二叉查找樹就基本上完成了，我們?yōu)樗鼘?shí)現(xiàn)了，添加、查找、刪除以及先中后三種遍歷方法
但是實(shí)際上這樣的二叉查找樹是存在一些問題的，當(dāng)我們不斷的添加更大/更小的元素的時候，會出現(xiàn)如下情況：
tree.insert(16) tree.insert(17) tree.insert(18)
來看看現(xiàn)在整顆樹的情況：
看圖片容易得出它是不平衡的，這又會引出平衡樹的概念，要解決這個問題，還需要更復(fù)雜的實(shí)現(xiàn)，例如：AVL樹，紅黑樹 哎，之后再慢慢去學(xué)習(xí)吧
相關(guān)文章：
二叉樹遍歷算法-php的示例
二叉樹的中序遍歷,該怎么解決
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
Copyright ? 2019-2024 51dongshi.com 版權(quán)所有
違法及侵權(quán)請聯(lián)系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市萬商天勤律師事務(wù)所王興未律師提供法律服務(wù)
