玖九九玖玖,久久精品视频、,大香蕉最新在线

當(dāng)你初學(xué)編程時(shí)，通常是將數(shù)組作為 “主要的數(shù)據(jù)結(jié)構(gòu)”來(lái)學(xué)習(xí)的。

最終，你也會(huì)學(xué)習(xí)到哈希表(hash tables)。如果你正在修計(jì)算機(jī)科學(xué)學(xué)位，你必須學(xué)習(xí)的一門課程是數(shù)據(jù)結(jié)構(gòu)。你還會(huì)學(xué)習(xí)到鏈表（linked list），隊(duì)列（queues）以及棧（stacks）。我們將這些數(shù)據(jù)結(jié)構(gòu)稱為“線性”數(shù)據(jù)結(jié)構(gòu)，因?yàn)樗羞@些數(shù)據(jù)結(jié)構(gòu)在邏輯上都有一個(gè)起點(diǎn)和終點(diǎn)。

當(dāng)我們開(kāi)始學(xué)習(xí)樹(shù)（trees）和圖（graphs）的時(shí)候，真的變得很困惑。我們不再以線性的方式存儲(chǔ)數(shù)據(jù)。這兩種數(shù)據(jù)結(jié)構(gòu)都以一種特殊的方式來(lái)存儲(chǔ)數(shù)據(jù)。

本文的目的是幫助你更好地理解樹(shù)這種數(shù)據(jù)結(jié)構(gòu)，并且澄清一些你可能存在的困惑。

在本文中，我們將學(xué)習(xí)以下內(nèi)容：

什么是樹(shù)
樹(shù)的示例
它的術(shù)語(yǔ)定義以及它怎么運(yùn)作
怎樣編碼實(shí)現(xiàn)樹(shù)這一數(shù)據(jù)結(jié)構(gòu)

讓我們擼起袖子開(kāi)始干吧。 :)

定義

在開(kāi)始編碼的時(shí)候，很常見(jiàn)的現(xiàn)象是對(duì)線性數(shù)據(jù)結(jié)構(gòu)的理解要好于樹(shù)和圖的理解。

樹(shù)是著名的非線性數(shù)據(jù)結(jié)構(gòu)。它們不是以線性的方式存儲(chǔ)數(shù)據(jù)。他們按照層級(jí)關(guān)系來(lái)組織數(shù)據(jù)。

一起來(lái)看一個(gè)生活中的真實(shí)例子

當(dāng)我說(shuō)層級(jí)關(guān)系的時(shí)候意味著什么？

想象一下包含幾代人的家譜：祖父母、父母、孩子、兄弟姐妹等。我們通常按照層級(jí)關(guān)系來(lái)組織家譜。

上面的這張圖片就是我的家譜：Tossico, Akikazu, Hitomi, 和 Takemi 是我的祖父母.

Toshiaki 和 Juliana 是我的父母。

TK, Yuji, Bruno, 和 Kaio 是我父母的孩子(我和我的兄弟姐妹)。

一個(gè)組織的架構(gòu)是層級(jí)關(guān)系的另一個(gè)范例。

在 HTML 中，Document Object Model (DOM) 也是按照樹(shù)的方式運(yùn)行。

HTML 標(biāo)簽會(huì)包含其他的標(biāo)簽。我們有一個(gè) head 標(biāo)簽和一個(gè) body 標(biāo)簽。這些標(biāo)簽包含特殊的組件。head 標(biāo)簽包含 meta 和 title 標(biāo)簽。body 標(biāo)簽包含用戶界面展示使用的組件，如 h1、a、li 等。

技術(shù)定義

樹(shù)是一系列節(jié)點(diǎn)（nodes）的集合。所有的節(jié)點(diǎn)通過(guò)邊（edge）連接。每一個(gè)節(jié)點(diǎn)包含數(shù)據(jù)，每一個(gè)節(jié)點(diǎn)可能有也可能沒(méi)有子節(jié)點(diǎn)。

我們將樹(shù)的第一個(gè)節(jié)點(diǎn)稱為根節(jié)點(diǎn)（root）。如果根節(jié)點(diǎn)與其他節(jié)點(diǎn)相連，那么這個(gè)根節(jié)點(diǎn)又是一個(gè)父節(jié)點(diǎn)，與它相連的節(jié)點(diǎn)稱為子節(jié)點(diǎn)。

所有的樹(shù)節(jié)點(diǎn)都是通過(guò)邊相連。邊是樹(shù)很重要的一部分，因?yàn)闃?shù)通過(guò)邊來(lái)管理節(jié)點(diǎn)之間的關(guān)系。

葉節(jié)點(diǎn)（leaves）是樹(shù)上最后的節(jié)點(diǎn)。葉節(jié)點(diǎn)就是那些沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。和真實(shí)的樹(shù)一樣，我們有樹(shù)根，有樹(shù)干，和樹(shù)葉。

另外兩個(gè)需要理解的重要概念是高度（height）和深度（depth）。

樹(shù)的高度是指到達(dá)樹(shù)葉的最長(zhǎng)路徑的長(zhǎng)度。

一個(gè)節(jié)點(diǎn)的深度是該節(jié)點(diǎn)到達(dá)根節(jié)點(diǎn)的路徑長(zhǎng)度。

術(shù)語(yǔ)總結(jié)

根節(jié)點(diǎn) 是樹(shù)上最頂部的節(jié)點(diǎn)
邊是節(jié)點(diǎn)之間的連接
子節(jié)點(diǎn) 是指擁有父節(jié)點(diǎn)的節(jié)點(diǎn)
父節(jié)點(diǎn) 是指和子節(jié)點(diǎn)之間有一條邊連接的節(jié)點(diǎn)
葉節(jié)點(diǎn) 是指樹(shù)中沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
高度是指到到達(dá)葉節(jié)點(diǎn)最長(zhǎng)路徑的長(zhǎng)度
深度是指一個(gè)節(jié)點(diǎn)到達(dá)根節(jié)點(diǎn)路徑的長(zhǎng)度

二叉樹(shù)（Binary trees）

現(xiàn)在我們來(lái)討論一種特殊的樹(shù)。我們稱之為二叉樹(shù)（Binary trees）。

"在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支（即不存在分支度大于2的節(jié)點(diǎn)）的樹(shù)結(jié)構(gòu)。通常分支被稱作“左子樹(shù)”或“右子樹(shù)”。二叉樹(shù)的分支具有左右次序，不能隨意顛倒。" -- 維基百科

所以我們一起來(lái)看一個(gè)二叉樹(shù)的示例：

編碼實(shí)現(xiàn)一個(gè)二叉樹(shù)

當(dāng)我們?cè)趯?shí)現(xiàn)一個(gè)二叉樹(shù)的時(shí)候，我們需要記住的第一件事情是：二叉樹(shù)是一系列節(jié)點(diǎn)的集合。每一個(gè)節(jié)點(diǎn)有3個(gè)屬性：值（values），左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

我們?cè)趺赐ㄟ^(guò)初始化這三個(gè)屬性來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的二叉樹(shù)呢？

一起來(lái)看一看：

class BinaryTree(val value: Any) {
    var leftChild: BinaryTree? = null
    var rightChild: BinaryTree? = null
    }

這就是我們的二叉樹(shù)類。

當(dāng)我們構(gòu)建一個(gè)對(duì)象的時(shí)候，我們將 value （節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)）作為一個(gè)參數(shù)傳遞進(jìn)去。注意 leftChild 和 rightChild 都被設(shè)置成了 null。

為什么？

因?yàn)楫?dāng)我們創(chuàng)建一個(gè)節(jié)點(diǎn)的時(shí)候，它沒(méi)有任何子節(jié)點(diǎn)。我們僅有節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)。

我們來(lái)測(cè)試一下：

fun testBinaryTree(){
    val tree = BinaryTree("a")
    println(tree.value) //a
    println(tree.leftChild) //null
    println(tree.rightChild) //null
}

就是這樣的。

我們可以將字符串 "a" 作為值傳遞給二叉樹(shù)節(jié)點(diǎn)。如果我們打印 tree.value, tree.leftChild 和 tree.rightChild 可以看到它們的值。

我們繼續(xù)插入部分。在這里我們需要做什么？

我們將實(shí)現(xiàn)一個(gè)方法，在左節(jié)點(diǎn)或者右節(jié)點(diǎn)插入一個(gè)節(jié)點(diǎn)。

規(guī)則是這樣的：

如果當(dāng)前節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，我們就創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將它設(shè)置成當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)。
如果當(dāng)前節(jié)點(diǎn)有左子節(jié)點(diǎn)，我們創(chuàng)建一個(gè)新的節(jié)點(diǎn)并將它放在當(dāng)前左子節(jié)點(diǎn)的位置。然后將左子節(jié)點(diǎn)放到新節(jié)點(diǎn)的左子節(jié)點(diǎn)。

我們來(lái)畫一下：

這里是代碼實(shí)現(xiàn)：

fun insertLeft(value: Any){
        if (leftChild==null){
            leftChild = BinaryTree(value)
        }else{
            val newNode = BinaryTree(value)
            newNode.leftChild = leftChild
            leftChild = newNode
        }
    }

再說(shuō)明一下，如果當(dāng)前節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，我們直接創(chuàng)建一個(gè)節(jié)點(diǎn)并將它賦值給左子節(jié)點(diǎn)。否則我們創(chuàng)建一個(gè)新的節(jié)點(diǎn)，將它的左子節(jié)點(diǎn)設(shè)置為當(dāng)前左子節(jié)點(diǎn)，然后再將新的節(jié)點(diǎn)設(shè)置為左子節(jié)點(diǎn)。

插入右子節(jié)點(diǎn)的邏輯是一樣的：

fun insertRight(value: Any){
        if (rightChild==null){
            rightChild = BinaryTree(value)
        }else{
            val newNode = BinaryTree(value)
            newNode.rightChild = rightChild
            rightChild = newNode
        }
    }

代碼實(shí)現(xiàn)完成了。

但是并不完整。我們還需要測(cè)試一下。

我們來(lái)構(gòu)建下面這樣一棵樹(shù)：

總結(jié)一下圖中的這個(gè)樹(shù)：

a 節(jié)點(diǎn)是我們這個(gè)二叉樹(shù)的根節(jié)點(diǎn)
a 的左子節(jié)點(diǎn)是 b 節(jié)點(diǎn)
a 的右子節(jié)點(diǎn)是 c 節(jié)點(diǎn)
b 的右子節(jié)點(diǎn)是 d 節(jié)點(diǎn)（b節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)）
c 的左子節(jié)點(diǎn)是 e 節(jié)點(diǎn)
c 的右子節(jié)點(diǎn)是 f 節(jié)點(diǎn)
e 節(jié)點(diǎn)和 f 節(jié)點(diǎn) 都沒(méi)有子節(jié)點(diǎn)

所以下面就是這個(gè)樹(shù)的代碼：

val aNode = BinaryTree("a")
   aNode.insertLeft("b")
   aNode.insertRight("c")

   val bNode = aNode.leftChild
   bNode?.insertRight("d")

   val cNode = aNode.rightChild
   cNode?.insertLeft("e")
   cNode?.insertRight("f")

   val dNode = bNode?.rightChild
   val eNode = cNode?.leftChild
   val fNode = cNode?.rightChild

   println(aNode.value) //a
   println(bNode?.value)//b
   println(cNode?.value)//c
   println(dNode?.value)//d
   println(eNode?.value)//e
   println(fNode?.value)//f

這樣插入算法就算完成了。

現(xiàn)在我們一起來(lái)看看樹(shù)的遍歷。

樹(shù)的遍歷我們有兩個(gè)選項(xiàng)：深度優(yōu)先搜索（Depth-First Search (DFS)） 和 廣度優(yōu)先搜索（Breadth-First Search (BFS)）

DFS：沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)，盡可能深的搜索樹(shù)的分支。當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過(guò)程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源節(jié)點(diǎn)并重復(fù)以上過(guò)程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問(wèn)為止 ---維基百科
BFS：是從根節(jié)點(diǎn)開(kāi)始，沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問(wèn)，則算法中止 ---維基百科

我們一起來(lái)實(shí)現(xiàn)每一種遍歷類型。

深度優(yōu)先搜索（DFS）

DFS 先要遍歷完到葉節(jié)點(diǎn)的所有路徑，然后再返回（backtracking'），之后再遍歷另外一個(gè)分支。我們來(lái)看一下這種遍歷的示例：

這個(gè)算法的結(jié)果是 1-2-3-4-5-6-7。

為什么？

我們來(lái)分解一下：

從根節(jié)點(diǎn)（1）開(kāi)始。打印
進(jìn)入左子節(jié)點(diǎn)（2），并打印
繼續(xù)進(jìn)入左子節(jié)點(diǎn)（3），并打印。（這個(gè)節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)）。
返回并進(jìn)入右子節(jié)點(diǎn)（4）并打印。（這個(gè)節(jié)點(diǎn)也沒(méi)有任何子節(jié)點(diǎn)）。
返回到根節(jié)點(diǎn)并進(jìn)入它的右子節(jié)點(diǎn)（5），并打印。
進(jìn)入左子節(jié)點(diǎn)（6）并打印。（這個(gè)節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)）。
返回并進(jìn)入右子節(jié)點(diǎn)（7）并打印。（這個(gè)節(jié)點(diǎn)也沒(méi)有任何子節(jié)點(diǎn)）。
結(jié)束

當(dāng)我們沿著樹(shù)的深度方向探索葉節(jié)點(diǎn)然后再返回時(shí)。這就是所謂的 DFS 算法。

現(xiàn)在我們已經(jīng)了解了這種遍歷算法，我們將討論三種類型的 DFS：前序、中序和后序。

前序

我們?cè)谏厦嬉粋€(gè)例子是中使用的就是前序。

先打印當(dāng)前節(jié)點(diǎn)的值。
如果當(dāng)前節(jié)點(diǎn)有左子節(jié)點(diǎn)（也只有它有左子節(jié)點(diǎn)時(shí)）則進(jìn)入左子節(jié)點(diǎn)并打印。
如果當(dāng)前節(jié)點(diǎn)有右子節(jié)點(diǎn)（也只有它有右子節(jié)點(diǎn)時(shí)）則進(jìn)入右子節(jié)點(diǎn)并打印。

fun preOrder(){
        println(value)
        leftChild?.preOrder()
        rightChild?.preOrder()
    }

中序

上面這個(gè)樹(shù)執(zhí)行中序算法后的結(jié)果是：3-2-4-1-6-5-7.

先左子樹(shù)，然后自己，最后右子樹(shù)。

來(lái)看一下代碼：

fun inOrder(){
        leftChild?.inOrder()
        println(value)
        rightChild?.inOrder()
    }

當(dāng)且僅當(dāng)有左子樹(shù)時(shí)，進(jìn)入左子樹(shù)并打印。
打印當(dāng)前節(jié)點(diǎn)的值。
當(dāng)且僅當(dāng)有右子樹(shù)時(shí)，進(jìn)入右子樹(shù)并打印。

后序

這個(gè)樹(shù)執(zhí)行后序算法以后的結(jié)果是： 3-4-2-6-7-5-1。

先左子樹(shù)、然后右子樹(shù)，最后是當(dāng)前節(jié)點(diǎn)。

代碼如下：

fun postOrder(){
        leftChild?.postOrder()
        rightChild?.postOrder()
        println(value)
    }

廣度優(yōu)先搜索（Breadth-First Search（BFS））

BFS 算法按照層次一級(jí)一級(jí)的遍歷樹(shù)

這個(gè)例子可以幫助我們更好地理解這個(gè)算法：

那么我們按層遍歷，在這個(gè)例子中產(chǎn)生的結(jié)果就是 1-2-5-3-4-6-7。

第0層/級(jí)：只有一個(gè)節(jié)點(diǎn)，值是 1
第1層/級(jí)：有兩個(gè)節(jié)點(diǎn)：2 和 5
第3層/級(jí)：有4個(gè)節(jié)點(diǎn)：3, 4, 6 和 7

我們來(lái)看一下編碼實(shí)現(xiàn)：

fun bfs(){
       val queue = ArrayQueue<BinaryTree>(10)
       queue.add(this)
       while (queue.isNotEmpty()){
           val currentNode = queue[0]
           queue.remove(currentNode)
           println(currentNode.value)

           currentNode.leftChild?.let { queue.add(it) }
           currentNode.rightChild?.let { queue.add(it) }
       }
   }

為了實(shí)現(xiàn) BFS 算法，我們借助了隊(duì)列數(shù)據(jù)結(jié)構(gòu)。

怎么實(shí)現(xiàn)的呢？

上圖：

首先將根節(jié)點(diǎn)放入隊(duì)列。
只要隊(duì)列不為空就一直迭代。
取出隊(duì)列中的第一個(gè)節(jié)點(diǎn)并打印它的值。
將當(dāng)前隊(duì)列的左右子節(jié)點(diǎn)放進(jìn)隊(duì)列（如果它有子節(jié)點(diǎn)的話）。
結(jié)束。在隊(duì)列的幫助下我們最終將打印出每一個(gè)節(jié)點(diǎn)的值。

二叉查找樹(shù)（Binary Search tree）

二叉查找樹(shù)又稱為有序二叉樹(shù)，它按照有序的方式存儲(chǔ)數(shù)據(jù)，所以查找以及其他操作都可以使用而二分查找的方式進(jìn)行。

二叉查找樹(shù)很重要的一個(gè)屬性是：二叉樹(shù)節(jié)點(diǎn)中的值要大于左子樹(shù)中的值但是小于右子樹(shù)中的值。

我們來(lái)分析一下上圖中的幾個(gè)樹(shù)：

A 是反轉(zhuǎn)后的二叉查找樹(shù)，7-5-8-6 子樹(shù)應(yīng)該在右邊，2-1-3 子樹(shù)應(yīng)該在左邊。
B 是唯一正確的選項(xiàng)。它滿足二叉查找樹(shù)的屬性。
C 有一個(gè)問(wèn)題，數(shù)值為4的那個(gè)節(jié)點(diǎn)應(yīng)該位于根節(jié)點(diǎn)的左邊，因?yàn)樗∮?5。

我們來(lái)編碼實(shí)現(xiàn)一個(gè)二叉查找樹(shù)

在這一節(jié)我們將了解在二叉查找樹(shù)中插入節(jié)點(diǎn)、搜索指定值、刪除節(jié)點(diǎn)以及樹(shù)的平衡。

插入往樹(shù)中添加一個(gè)新的節(jié)點(diǎn)

假設(shè)我們有一個(gè)空的樹(shù)，我們想按照以下順序添加這些值：50，76，21，4，32，100，64，52。

第一件事是我們需要確認(rèn) 50 是否是我們這個(gè)樹(shù)的根。

然后我們就可以一個(gè)一個(gè)地添加節(jié)點(diǎn)。

76 比 50 大，所以 76 插入到右邊
21 比 50 小，所以 21 插入到坐標(biāo)
4 比 50 小，50 這個(gè)節(jié)點(diǎn)有左子節(jié)點(diǎn) 21，由于 4 比 21 小，所以將 4 插入到節(jié)點(diǎn) 21 的左邊
32 比 50小，50 這個(gè)節(jié)點(diǎn)有左子節(jié)點(diǎn) 21，由于 32 比21 大，所以將 32 插入到 21 的右邊
100 比 50 大，50 這個(gè)節(jié)點(diǎn)有右子節(jié)點(diǎn) 76，由于 100 比 76 大，所以將 100 插入到 76 的右邊
64 比 50 大，50 這個(gè)節(jié)點(diǎn)有右子節(jié)點(diǎn) 76，64 比76小，所以將 64 插入到 76 的左邊
52 比 50 大，50 這個(gè)節(jié)點(diǎn)有右子節(jié)點(diǎn) 76，52 比 76 小，76 有左子節(jié)點(diǎn) 64，52 比 64 小，所以將 52 插入到 64 的左側(cè)

你有注意到這個(gè)規(guī)律嗎？

我們來(lái)分解一下：

新的值比當(dāng)前節(jié)點(diǎn)的值大還是小？
如果比當(dāng)前節(jié)點(diǎn)的值大，進(jìn)入右子樹(shù)。如果當(dāng)前節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn)，則將它插入到右子節(jié)點(diǎn)，否則回到第一步。
如果比當(dāng)前節(jié)點(diǎn)的值小，進(jìn)入左子樹(shù)。如果當(dāng)前節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，則將它插入到左子節(jié)點(diǎn)，否則回到第一步。
有一種情況我們沒(méi)有處理，那就是新插入的值和當(dāng)前節(jié)點(diǎn)的值相等。這個(gè)時(shí)候我們使用規(guī)則3，將相等的值插入到左子樹(shù)。

一起來(lái)看一下編碼：

class BinarySearchTree(private var value:  Int){
   var leftChild : BinarySearchTree? = null
   var rightChild: BinarySearchTree? = null

   fun insertNode(insertValue: Int){
       if (insertValue <= value){
           leftChild?.insertNode(insertValue)
           if (leftChild == null) {
               leftChild = BinarySearchTree(insertValue)
           }
       }
       if (insertValue > value){
           rightChild?.insertNode(insertValue)
           if (rightChild==null){
               rightChild = BinarySearchTree(insertValue)
           }
       }
   }

看起來(lái)非常簡(jiǎn)單。
這個(gè)算法的強(qiáng)大之處是遞歸部分，也就是第 7 行和第 12 行。這兩行分別調(diào)用了左右子節(jié)點(diǎn)的 insertMode 方法。第 9 行和第 14 行就是將新插入的值放入當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。

我們?cè)賮?lái)看一下查找

查找算法就是有關(guān)搜索。對(duì)于給定的值（整數(shù)），我們需要確認(rèn)我們的二叉查找樹(shù)中是否包含這個(gè)值。

在插入算法中有一個(gè)很重要的點(diǎn)需要我們注意。首先我們有一個(gè)根節(jié)點(diǎn)，然后所有左子樹(shù)節(jié)點(diǎn)中的值都比根節(jié)點(diǎn)要小，所有右子樹(shù)節(jié)點(diǎn)中的值都要大于根節(jié)點(diǎn)。

我們一起來(lái)看一個(gè)例子。

假設(shè)我們有這樣一個(gè)樹(shù)：

現(xiàn)在我們需要確認(rèn)樹(shù)中是否有一個(gè)節(jié)點(diǎn)的值是52.

我們來(lái)分解一下

我們從根節(jié)點(diǎn)開(kāi)始，也就是當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)。給定的值比當(dāng)前節(jié)點(diǎn)的值?。咳绻?，我們進(jìn)入左子樹(shù)開(kāi)始查找。
給定的值比當(dāng)前節(jié)點(diǎn)的值大？如果是，則進(jìn)入右子樹(shù)開(kāi)始查找。
如果規(guī)則1和2都不滿足，我們將給定值和當(dāng)前節(jié)點(diǎn)值比較，兩者是否相等？如果相等，返回 true，否則返回 false。

一起來(lái)看一下代碼：

fun findNode(searchValue : Int): Boolean{
        if (searchValue<value &&  leftChild != null){
            return leftChild!!.findNode(searchValue)
        }

        if (searchValue > value && rightChild != null){
            return rightChild!! .findNode(searchValue)
        }

        return searchValue == value
    }

第 2、3 行是遵循規(guī)則1
第 6、7 行是遵循規(guī)則2
第 9 行是遵循規(guī)則3

我們?cè)趺磥?lái)測(cè)試一下呢？
我們先創(chuàng)建一個(gè)二叉搜索時(shí)，并將根節(jié)點(diǎn)的值初始化為 15。

val tree = BinarySearchTree(15)

然后再插入很多新的節(jié)點(diǎn)。

bsfTree.insertNode(10)
   bsfTree.insertNode(8)
   bsfTree.insertNode(20)
   bsfTree.insertNode(12)
   bsfTree.insertNode(17)
   bsfTree.insertNode(25)
   bsfTree.insertNode(19)

對(duì)于已經(jīng)插入的每一個(gè)節(jié)點(diǎn)，我們可以測(cè)試一下我們的 findMode 方法是否正常運(yùn)行。

   println(tree.findNode(15))
   println(tree.findNode(10))
   println(tree.findNode(8))
   println(tree.findNode(12))
   println(tree.findNode(20))
   println(tree.findNode(17))
   println(tree.findNode(25))
   println(tree.findNode(19))

不錯(cuò)，對(duì)于這些給定的值都能夠正常的查找到。我們來(lái)試一下二叉查找樹(shù)中沒(méi)有的值：

println(tree.findNode(0))

完美！

刪除：移除以及重新組織節(jié)點(diǎn)

刪除操作要復(fù)雜得多，因?yàn)槲覀円紤]各種不同的情況。對(duì)于給定的值，我們需要找到值和它一樣的節(jié)點(diǎn)并刪除它。想象一下這個(gè)節(jié)點(diǎn)有以下這樣一些場(chǎng)景：它沒(méi)有子節(jié)點(diǎn)，它有一個(gè)子節(jié)點(diǎn)，它有兩個(gè)子節(jié)點(diǎn)。

場(chǎng)景1：這個(gè)節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)（它是一個(gè)葉節(jié)點(diǎn)）

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|

如果我們需要?jiǎng)h除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，我們只需要簡(jiǎn)單的將它刪除就可以。這個(gè)時(shí)候不需要重新組織數(shù)據(jù)。

場(chǎng)景2：這個(gè)節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn)（左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)）

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /            
# |20|

這種情況下，我們需要將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)指向子節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)是左子節(jié)點(diǎn)，我們需要將父節(jié)點(diǎn)的左子節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)是右子節(jié)點(diǎn)，我們需要將父節(jié)點(diǎn)的右子節(jié)點(diǎn)指向子節(jié)點(diǎn)。

場(chǎng)景3：這個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|                        |20|

當(dāng)一個(gè)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)的時(shí)候，我們需要從它的右子節(jié)點(diǎn)開(kāi)始找到右子樹(shù)中值最小的那個(gè)節(jié)點(diǎn)，然后將這個(gè)當(dāng)前節(jié)點(diǎn)的值用查找到的最小值替換，將最小的那個(gè)節(jié)點(diǎn)刪除。

還是來(lái)看一看代碼吧

fun removeNode(deleteValue: Int, parent: BinarySearchTree?): Boolean{
        if (deleteValue < value) {
            //待刪除的值比當(dāng)前節(jié)點(diǎn)小

            //當(dāng)前節(jié)點(diǎn)只有左子節(jié)點(diǎn)，在左子節(jié)點(diǎn)中繼續(xù)刪除
            leftChild?.let { return it.removeNode(deleteValue,this) }

            //無(wú)左子節(jié)點(diǎn)，直接返回刪除失敗
            return false
        }else if (deleteValue > value) {
            //待刪除的值比當(dāng)前節(jié)點(diǎn)大

            //當(dāng)前節(jié)點(diǎn)只有右子節(jié)點(diǎn)，在右子節(jié)點(diǎn)中繼續(xù)刪除
            rightChild?.let { return it.removeNode(deleteValue, this) }

            //無(wú)右子節(jié)點(diǎn)，直接返回刪除失敗
            return false
        }else {
            //待刪除的值與當(dāng)前節(jié)點(diǎn)相等，需要?jiǎng)h除當(dāng)前節(jié)點(diǎn)

            if (leftChild == null && rightChild == null && parent?.leftChild === this){
                //當(dāng)前節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)，為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，將父節(jié)點(diǎn)的左子節(jié)點(diǎn)置空
                parent.leftChild = null
            }else if (leftChild == null && rightChild == null && parent?.rightChild === this){
                //當(dāng)前節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)，為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，將父節(jié)點(diǎn)的右子節(jié)點(diǎn)置空
                parent.rightChild = null
            }else if (leftChild != null && rightChild == null && parent?.leftChild === this){
                //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)（左），為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，將父節(jié)點(diǎn)的左子節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)
                parent.leftChild = leftChild
            }else if (leftChild != null && rightChild == null && parent?.rightChild === this){
                //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)（左），為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，將父節(jié)點(diǎn)的右子節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)
                parent.rightChild = leftChild
            }else if (rightChild != null && leftChild == null && parent?.leftChild === this){
                //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)（右），為父節(jié)點(diǎn)的左子節(jié)點(diǎn)，將父節(jié)點(diǎn)的左子節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)
                parent.leftChild = rightChild
            }else if(rightChild != null && leftChild == null && parent?.rightChild === this){
                //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)（右），為父節(jié)點(diǎn)的右子節(jié)點(diǎn)，將父節(jié)點(diǎn)的右子節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)
                parent.rightChild = rightChild
            }else{
                //當(dāng)前節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的值設(shè)為右子樹(shù)中的最小值，并將這個(gè)最小值從右子樹(shù)中刪除
                val minValue = rightChild!!.findMiniumValue()
                value = minValue
                rightChild!!.removeNode(minValue, this)
            }
            return true
        }
    }

首先：注意參數(shù) deleteValue 和 parent。我們要找到保存 deleteValue 的節(jié)點(diǎn)，并且要將這個(gè)節(jié)點(diǎn)從它的父節(jié)點(diǎn)中移除。
第二：注意返回值。我們的算法會(huì)返回一個(gè)布爾值。如果查找成功并刪除則返回 true。否則返回 false。
從第3行到第17行：我們開(kāi)始搜索持有 deleteValue 的節(jié)點(diǎn)。如果 deleteValue 比當(dāng)前節(jié)點(diǎn)的值小，進(jìn)入左子樹(shù)然后遞歸（當(dāng)然這必須是在當(dāng)前節(jié)點(diǎn)有左子節(jié)點(diǎn)的情況）。如果 deleteValue 比當(dāng)前節(jié)點(diǎn)的值大，進(jìn)入右子樹(shù)然后遞歸。
第18行：我們開(kāi)始刪除算法。詳細(xì)的步驟就不啰嗦了，都寫在注釋里了。

為了找到右子樹(shù)中的最小值，我們定義了 findMiniumValue 方法，沿著左字節(jié)點(diǎn)一直往下，當(dāng)不再有左子節(jié)點(diǎn)時(shí)，我們就找到了最小值：

fun findMiniumValue(): Int{
        return leftChild?.findMiniumValue()?:value
    }

現(xiàn)在我們來(lái)測(cè)試一下：

我們將使用下面這個(gè)樹(shù)來(lái)測(cè)試我們的removeNode 方法

#        |15|
#      /      \
#    |10|     |20|
#   /    \    /    \
# |8|   |12| |17| |25|
#              \
#              |19|

首先來(lái)刪除值為8的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)。

fun  testDeleteNode(){
    val bsfTree = BinarySearchTree(15)
    bsfTree.insertNode(10)
    bsfTree.insertNode(8)
    bsfTree.insertNode(20)
    bsfTree.insertNode(12)
    bsfTree.insertNode(17)
    bsfTree.insertNode(19)
    bsfTree.insertNode(25)

    bsfTree.preOrder()

    println(bsfTree.removeNode(8, null))
    bsfTree.preOrder()
    
}

#     |15|
#   /      \
# |10|     |20|
#    \    /    \
#   |12| |17| |25|
#          \
#          |19|

接下來(lái)刪除值為17的節(jié)點(diǎn)，它只有一個(gè)子節(jié)點(diǎn)。

println(bsfTree.removeNode(17, null))
    bsfTree.preOrder()

#        |15|
#      /      \
#    |10|     |20|
#       \    /    \
#      |12| |19| |25|

最后我們刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)，那就是我們這個(gè)樹(shù)的根節(jié)點(diǎn)。

println(bsfTree.removeNode(15, null))
    bsfTree.preOrder()
    
#        |19|
#      /      \
#    |10|     |20|
#        \        \
#        |12|     |25|

本文譯自：Everything you need to know about tree data structures，原文編碼為 python，翻譯過(guò)程中使用了 kotlin 語(yǔ)言。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)：樹(shù)

數(shù)據(jù)結(jié)構(gòu)：樹(shù)

定義

一起來(lái)看一個(gè)生活中的真實(shí)例子

技術(shù)定義

術(shù)語(yǔ)總結(jié)

二叉樹(shù)（Binary trees）

編碼實(shí)現(xiàn)一個(gè)二叉樹(shù)

深度優(yōu)先搜索（DFS）

前序

中序

后序

廣度優(yōu)先搜索（Breadth-First Search（BFS））

二叉查找樹(shù)（Binary Search tree）

我們來(lái)編碼實(shí)現(xiàn)一個(gè)二叉查找樹(shù)

插入往樹(shù)中添加一個(gè)新的節(jié)點(diǎn)

我們?cè)賮?lái)看一下查找

刪除：移除以及重新組織節(jié)點(diǎn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)：樹(shù)

定義

一起來(lái)看一個(gè)生活中的真實(shí)例子

技術(shù)定義

術(shù)語(yǔ)總結(jié)

二叉樹(shù)（Binary trees）

編碼實(shí)現(xiàn)一個(gè)二叉樹(shù)

深度優(yōu)先搜索（DFS）

前序

中序

后序

廣度優(yōu)先搜索（Breadth-First Search（BFS））

二叉查找樹(shù)（Binary Search tree）

我們來(lái)編碼實(shí)現(xiàn)一個(gè)二叉查找樹(shù)

插入往樹(shù)中添加一個(gè)新的節(jié)點(diǎn)

我們?cè)賮?lái)看一下查找

刪除：移除以及重新組織節(jié)點(diǎn)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av