原來(lái)來(lái)自 呆萌數(shù)據(jù)結(jié)構(gòu)-06二叉查找樹?imoegirl.com

二叉查找樹（Binary Search Tree），簡(jiǎn)寫B(tài)ST，是滿足某些條件的特殊二叉樹。任何一個(gè)節(jié)點(diǎn)的左子樹上的點(diǎn)，都必須小于當(dāng)前節(jié)點(diǎn)。任何一個(gè)節(jié)點(diǎn)的右子樹上的點(diǎn)，都必須大于當(dāng)前節(jié)點(diǎn)。任何一棵子樹，也都滿足上面兩個(gè)條件。另外二叉查找樹中，是不存在重復(fù)節(jié)點(diǎn)的。

上圖中的二叉查找樹，我們從Root節(jié)點(diǎn)3開始看，它的左子樹（1，2） 和右子樹（6，4，9，7）分別滿足條件，左子樹上的點(diǎn)，都小于當(dāng)前節(jié)點(diǎn)，右子樹上的點(diǎn)，都大于當(dāng)前節(jié)點(diǎn)。

繼續(xù)，我們以6作為起點(diǎn)，來(lái)看一下這棵子樹，6的左子樹（4），右子樹（9，7）也滿足上面兩條規(guī)則。

整棵樹中，任何一個(gè)點(diǎn)下面的子樹，都滿足上面提到的兩條規(guī)則。你現(xiàn)在是不是對(duì)Binary Search Tree已經(jīng)有一個(gè)大概的形象概念了。

為什么叫做二叉查找樹呢

因?yàn)樵贐ST中搜索一個(gè)值是非常簡(jiǎn)單和高效的。

看上面的樹，假設(shè)要搜索7這個(gè)節(jié)點(diǎn)。首先從Root節(jié)點(diǎn)出發(fā)，我們知道7大于3，所以會(huì)走到右子樹6，然后因?yàn)?也大于6，所以會(huì)繼續(xù)往右子樹走，到了9，因?yàn)?小于9，所以會(huì)向左子樹走，走到7，發(fā)現(xiàn)7等于7，所以找到要搜索的節(jié)點(diǎn)。

二叉樹的一些性質(zhì)

• 將任何一個(gè)點(diǎn)看作Root節(jié)點(diǎn)，則這個(gè)點(diǎn)的左子樹也是 Binary Search Tree
• 將任何一個(gè)點(diǎn)看作Root節(jié)點(diǎn)，則這個(gè)點(diǎn)的右子樹也是 Binary Search Tree
• Binary Search Tree中的最小節(jié)點(diǎn)，一定是整棵樹中最左下的葉子節(jié)點(diǎn)(從Root開始一直順著左子樹往下走，直到某一個(gè)點(diǎn)沒(méi)有左子節(jié)點(diǎn)，則這個(gè)點(diǎn)就是最小的)
• Binary Search Tree中的最大節(jié)點(diǎn)，一定是整棵樹中最右下的葉子節(jié)點(diǎn)(從Root開始一直順著右子樹往下走，直到某一個(gè)點(diǎn)沒(méi)有右子節(jié)點(diǎn)，則這個(gè)點(diǎn)就是最大的)

怎樣構(gòu)建和插入節(jié)點(diǎn)

向BST中插入一個(gè)節(jié)點(diǎn)，也是一個(gè)構(gòu)建的過(guò)程，和上面的搜索思路基本一樣。首先從Root開始，如果Root點(diǎn)為空，則直接構(gòu)建Root點(diǎn)。如果Root點(diǎn)不為空，則要判斷要插入的值，比Root點(diǎn)的值大還是小，如果小，則往左子樹走，如果大，則往右子樹走。直到走到某一個(gè)點(diǎn)，我們稱為點(diǎn)X，發(fā)現(xiàn)要插入的值，小于那個(gè)點(diǎn)X的值，并且點(diǎn)X沒(méi)有左子樹，則要插入的點(diǎn)作為X的左子節(jié)點(diǎn)。或者，要插入的點(diǎn)大于X，并且X沒(méi)有右子樹，則要插入的點(diǎn)作為X的右子節(jié)點(diǎn)。

下面是代碼實(shí)現(xiàn)（為了方便后面的刪除邏輯，我們每一個(gè)點(diǎn)，包含了指向左子樹，右子樹，以及父節(jié)點(diǎn)的引用）

// 這里先定義出節(jié)點(diǎn)的結(jié)構(gòu) class Node {public int data;public Node parent;public Node left;public Node right;public Node(int _data){this.data = _data;} }// 定義二叉搜索樹結(jié)構(gòu) class BST {private Node root;// 這個(gè)函數(shù)是 private 的，遞歸調(diào)用，插入節(jié)點(diǎn)private Node RecursionInsert(Node node, int data){if (node == null){return new Node(data);}if (data < node.data){node.left = RecursionInsert(node.left, data);node.left.parent = node;}else if (data > node.data){node.right = RecursionInsert(node.right, data);node.right.parent = node;}return node;}// 對(duì)外開放的 插入 接口public void Insert(int data){if (root == null){root = RecursionInsert(root, data);}else{RecursionInsert(root, data);}}// 按層序打印二叉樹public void LevelOrderTraversal(){Queue<Node> q = new Queue<Node>();q.Enqueue(root);while (q.Count > 0){Node currNode = q.Dequeue();if (currNode.left != null){q.Enqueue(currNode.left);}if (currNode.right != null){q.Enqueue(currNode.right);}// 括號(hào)里面是父節(jié)點(diǎn)的值string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");Debug.Log(msg);}} }// 創(chuàng)建一個(gè)二叉搜索樹 class Program {/* Let us create following BST50/ 30 70/ / 20 40 60 80 */static void Main(string[] args){BST bst = new BST();bst.Insert(50);bst.Insert(30);bst.Insert(20);bst.Insert(40);bst.Insert(70);bst.Insert(60);bst.Insert(80);bst.LevelOrderTraversal();} }

上面的代碼，首先定義了每一個(gè) Node 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，然后定義了二叉查找樹的結(jié)構(gòu)類，最后是C#調(diào)用BST的插入和打印方法。插入節(jié)點(diǎn)這里使用了遞歸的機(jī)結(jié)構(gòu)，還可以使用非遞歸，循環(huán)的形式去插入。

從最簡(jiǎn)單的開始，刪除一個(gè)節(jié)點(diǎn)

從 BST 中刪除節(jié)點(diǎn)，是相比來(lái)說(shuō)比較復(fù)雜的，復(fù)雜，也只是相對(duì)于插入來(lái)說(shuō)。只要理清幾種不同的情況，也就不復(fù)雜了。看過(guò)很多教程，一上來(lái)就是羅列各個(gè)情況，然后上代碼展示，如果是第一次學(xué)習(xí) BST，可能會(huì)有一點(diǎn)抽象。我們先不考慮代碼怎么實(shí)現(xiàn)，先從語(yǔ)言上把這個(gè)事情講明白，最后再看代碼。

從 BST 中刪除節(jié)點(diǎn)其實(shí)很容易，只要改變一下指針就可以了，重點(diǎn)是，刪除了一個(gè)節(jié)點(diǎn)后，還要讓整棵 BST 依然保持一個(gè)正確的結(jié)構(gòu)，這就是我們要做的。一切從最簡(jiǎn)單開始。

上面的圖中，我們要?jiǎng)h除一個(gè)葉子節(jié)點(diǎn)，就是左邊的數(shù)據(jù)為3的那個(gè)節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)是4，我們只需要將4這個(gè)節(jié)點(diǎn)中指向左子樹的指針設(shè)置為空，就可以了。這是很容易理解的。而刪除右邊的葉子節(jié)點(diǎn)，也是一樣的。就像下面的圖。

我們刪除18這個(gè)節(jié)點(diǎn)，只需要將13這個(gè)節(jié)點(diǎn)中指向右子樹的指針設(shè)置為空，即可。

上面說(shuō)的，就是刪除操作中最簡(jiǎn)單的一種情況，刪除葉子節(jié)點(diǎn)。還有一個(gè)很重要的點(diǎn)要注意，在刪除的時(shí)候，要判斷要?jiǎng)h除的節(jié)點(diǎn)是不是 Root 節(jié)點(diǎn)，也就是說(shuō)，整棵樹只有一個(gè)節(jié)點(diǎn)的情況，這樣的話還需要將 Root 節(jié)點(diǎn)設(shè)為空。Root節(jié)點(diǎn)的父節(jié)點(diǎn)，是永遠(yuǎn)為空的。

注意: 記住，現(xiàn)在不要考慮代碼實(shí)現(xiàn)的問(wèn)題，一定要先理解思路，文章的最后，會(huì)上代碼的。

關(guān)于節(jié)點(diǎn)刪除，加大一點(diǎn)點(diǎn)難度

接下來(lái)我們加大一點(diǎn)點(diǎn)難度。看下面的圖 (可以忽略圖中的紅色字，只看樹的節(jié)點(diǎn)結(jié)構(gòu))

我們要?jiǎng)h除左邊圖中5這個(gè)節(jié)點(diǎn)，而5這個(gè)節(jié)點(diǎn)只擁有一個(gè)子樹，就是左子樹。而5的父節(jié)點(diǎn)是2，它是2的右子樹。我們要?jiǎng)h除5，只需要將2的右子樹，指向5的子樹就可以 (這里其實(shí)不太關(guān)心5的子樹是左子樹還是右子樹)。簡(jiǎn)單來(lái)說(shuō)，就是將2原本指向5的指針，改為指向5的子樹，即可。就是右邊圖的樣子。

我們剛才刪除的5節(jié)點(diǎn)，只有左子樹，再看一個(gè)要?jiǎng)h除的節(jié)點(diǎn)只有右子樹的情況。

上面的圖中， 我們要?jiǎng)h除3這個(gè)節(jié)點(diǎn)，而這個(gè)節(jié)點(diǎn)只有右子樹。3的父親節(jié)點(diǎn)是2，所以，我們只需要將2原本指向3節(jié)點(diǎn)的指針，改為指向3的子樹即可。就像右邊的圖那樣。

不要著急，慢慢體會(huì)一下。在上面兩種情況沒(méi)有徹底理解思路之前，先不要往下看，否則可能會(huì)更困惑。

注意: 因?yàn)槲覀兊?Node 結(jié)構(gòu)中加入了一個(gè)指向父節(jié)點(diǎn)的指針，所以在刪除節(jié)點(diǎn)的時(shí)候，還要注意更新某些節(jié)點(diǎn)的 parent 指針指向。

更復(fù)雜的情況，先聊一下后繼節(jié)點(diǎn)

如果上面只是小打小鬧，那接下來(lái)，就是直面恐懼，噢不，直面復(fù)雜時(shí)刻啦，哈哈哈~

最復(fù)雜的一種情況，就是要?jiǎng)h除的節(jié)點(diǎn)，即有左子樹，又有右子樹。在說(shuō)這種情況怎么操作之前，我們先來(lái)說(shuō)一個(gè)前提概念，叫做后繼節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)，嚴(yán)肅點(diǎn)說(shuō)就是在中序遍歷的時(shí)候，遍歷完當(dāng)前節(jié)點(diǎn)后，下一個(gè)要訪問(wèn)的節(jié)點(diǎn)，就是當(dāng)前的節(jié)點(diǎn)的后繼節(jié)點(diǎn)。好吧，通俗點(diǎn)來(lái)講，就是假設(shè)在遍歷一棵樹時(shí)，訪問(wèn)完 1 號(hào)節(jié)點(diǎn)，如果接下來(lái)訪問(wèn)的是3號(hào)節(jié)點(diǎn)，那3號(hào)節(jié)點(diǎn)就是1的后繼節(jié)點(diǎn)。

那一個(gè)點(diǎn)的后繼節(jié)點(diǎn)怎么找呢？這個(gè)就很簡(jiǎn)單了。假設(shè)我們要找節(jié)點(diǎn) A 的后繼節(jié)點(diǎn)，那就是從 A 這個(gè)點(diǎn)的右子樹開始，一路向左走，走到某一個(gè)節(jié)點(diǎn)沒(méi)有左子樹可以往下走了，那這個(gè)節(jié)點(diǎn)，就是 A 的后繼節(jié)點(diǎn) (注意，這個(gè)后繼節(jié)點(diǎn)有可能是葉子節(jié)點(diǎn)，也有可能不是)。看下面的圖。

我們先看左邊部分的圖，我們要找節(jié)點(diǎn) 9 的后繼節(jié)點(diǎn)。按上面的規(guī)則，從節(jié)點(diǎn) 9 的右子樹 15 開始，依次往左走，先到達(dá) 15 判斷一下是否可以走，可以，我們走到 13，再判斷一下是否可以繼續(xù)往左走，可以，走到 11，然后再看是否可以繼續(xù)往左走，發(fā)現(xiàn)不可以了，那 11 就是節(jié)點(diǎn) 9 的后繼節(jié)點(diǎn)。

再看右邊部分的圖，我們要找節(jié)點(diǎn) 6 的后繼節(jié)點(diǎn)。按上面的規(guī)則從右子樹 11 開始，判斷是否可以往左走，可以，走到 8，再判斷是一下是否可以繼續(xù)往左走，發(fā)現(xiàn) 8 已經(jīng)沒(méi)有左子樹可以往下走了，所以 8 就是節(jié)點(diǎn) 6 的后繼節(jié)點(diǎn)。

最后一種刪除節(jié)點(diǎn)的情況

理解了后繼節(jié)點(diǎn)，就可以來(lái)說(shuō)最后一種，也是最復(fù)雜的一種刪除節(jié)點(diǎn)的情況了。就是要?jiǎng)h除的節(jié)點(diǎn)，即有左子樹，又有右子樹。操作的流程是這樣的。假設(shè)我們要?jiǎng)h除的節(jié)點(diǎn)是 A，第一步，我們要找到 A 的后繼節(jié)點(diǎn)。第二步，用 A 的后繼節(jié)點(diǎn)數(shù)據(jù)，替換要?jiǎng)h除的節(jié)點(diǎn) A 的數(shù)據(jù)。第三步，刪除后繼節(jié)點(diǎn)。（因?yàn)楹罄^節(jié)點(diǎn)要么是葉子節(jié)點(diǎn)，要么只有右子樹，所以刪除比較簡(jiǎn)單，就按之前聊過(guò)的刪除方法即可）。下面用示例解釋

上圖中，從第一個(gè)圖開始看，我們要?jiǎng)h除數(shù)據(jù)為 9 的節(jié)點(diǎn)。第一步，將要?jiǎng)h除的節(jié)點(diǎn)使用一個(gè)指針指向。第二步，看第二個(gè)圖，找到 9 節(jié)點(diǎn)的后繼節(jié)點(diǎn)，也就是 11。第三步，看第三張圖，用后繼節(jié)點(diǎn)的數(shù)據(jù)，替換要?jiǎng)h除的節(jié)點(diǎn)的數(shù)據(jù)，也就是用 11 替換 9。第四步，也就是最后一個(gè)圖，刪除后繼節(jié)點(diǎn) 11。到此，刪除操作完成。

接下來(lái)再看一個(gè)示例

上圖中，我們要?jiǎng)h除節(jié)點(diǎn) 6，還是先找到 6 的后繼節(jié)點(diǎn) 8，然后用節(jié)點(diǎn) 8 的數(shù)據(jù)，替換我們要?jiǎng)h除的節(jié)點(diǎn) 6 的數(shù)據(jù)(第三個(gè)小圖)。接下來(lái)就是刪除后繼節(jié)點(diǎn) 8，這里要注意，我們跟著箭頭的方向，看第四個(gè)小圖。在刪除后繼節(jié)點(diǎn) 8 時(shí)，我們發(fā)現(xiàn)節(jié)點(diǎn) 8 不是葉子節(jié)點(diǎn)，而是有右子樹，所以我們需要將節(jié)點(diǎn) 8 的父節(jié)點(diǎn)，原本指向 8 的指針，改為指向 8 的右子樹。也就是上圖中將節(jié)點(diǎn) 11 的左指針，改為指向節(jié)點(diǎn) 9，然后就是最后一個(gè)小圖的情況。（因?yàn)槲覀兊?Node 結(jié)構(gòu)中擁有 parent 指針，所以要記得把節(jié)點(diǎn) 9 的parent 指針從原來(lái)指向 8 改為現(xiàn)在指向 9）。到此，刪除節(jié)點(diǎn)結(jié)束。

接下來(lái)，我們展示完整的代碼

using System; using System.Collections.Generic;static class Debug {public static void Log(string msg){Console.WriteLine(msg);} }class Node {public int data;public Node parent;public Node left;public Node right;public Node(int _data){this.data = _data;Console.WriteLine("Insert: " + this.data);} }class BST {private Node root;private Node RecursionInsert(Node node, int data){if (node == null){return new Node(data);}if (data < node.data){node.left = RecursionInsert(node.left, data);node.left.parent = node;}else if (data > node.data){node.right = RecursionInsert(node.right, data);node.right.parent = node;}return node;}// 插入一個(gè)數(shù)據(jù)public void Insert(int data){if (root == null){root = RecursionInsert(root, data);}else{RecursionInsert(root, data);}}// 刪除節(jié)點(diǎn)public void DeleteNode(int data){Node delNode = root;// 首先要找到待刪除的節(jié)點(diǎn)while (delNode != null){if (delNode.data == data){break;}if (data < delNode.data){delNode = delNode.left;}else if (data > delNode.data){delNode = delNode.right;}}if (delNode == null){Debug.Log("Not found " + data);return;}// 要?jiǎng)h除的節(jié)點(diǎn)即沒(méi)有左子樹，也沒(méi)有右子樹，是葉子節(jié)點(diǎn)，或者是 Root 節(jié)點(diǎn)if (delNode.left == null && delNode.right == null){Node parent = delNode.parent;if (parent == null){root = null;}else{if (parent.left == delNode){parent.left = null;}else{parent.right = null;}}}else if (delNode.left != null && delNode.right == null){// 要?jiǎng)h除的節(jié)點(diǎn)只有左子樹的情況Node parent = delNode.parent;Node child = delNode.left;if (parent == null){root = child;root.parent = null;}else{if (parent.left == delNode){parent.left = child;}else{parent.right = child;}child.parent = parent;}}else if (delNode.right != null && delNode.left == null){// 要?jiǎng)h除的節(jié)點(diǎn)只有右子樹的情況Node parent = delNode.parent;Node child = delNode.right;if (parent == null){root = child;root.parent = null;}else{if (parent.left == delNode){parent.left = child;}else{parent.right = child;}child.parent = parent;}}else if (delNode.left != null && delNode.right != null){// 要?jiǎng)h除的節(jié)點(diǎn)即有左子樹，也有右子樹的情況// 首先找到后繼節(jié)點(diǎn)Node successorNode = FindMinimumLeftValue(delNode.right);delNode.data = successorNode.data;// 如果后繼節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則直接刪除即可if (successorNode.left == null && successorNode.right == null){if (successorNode.parent.left == successorNode){successorNode.parent.left = null;}else{successorNode.parent.right = null;}}else{// 如果后繼節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，要將后繼節(jié)點(diǎn)的父節(jié)點(diǎn)指向后繼節(jié)點(diǎn)的子樹，// 同時(shí)，修改子樹父節(jié)點(diǎn)的指針Node successorChild = successorNode.left != null ? successorNode.left : successorNode.right;Node parent = successorNode.parent;if (parent.left == successorNode){parent.left = successorChild;}else{parent.right = successorChild;}successorChild.parent = parent;}}}// 找到一顆子樹的最小左節(jié)點(diǎn)public Node FindMinimumLeftValue(Node fromNode){Node opt = fromNode;while (opt.left != null){opt = opt.left;}return opt;}public void LevelOrderTraversal(){Queue<Node> q = new Queue<Node>();q.Enqueue(root);while (q.Count > 0){Node currNode = q.Dequeue();if (currNode.left != null){q.Enqueue(currNode.left);}if (currNode.right != null){q.Enqueue(currNode.right);}string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");Debug.Log(msg);}} }class Program {/* Let us create following BST50/ 30 70/ / 20 40 60 80 */static void Main(string[] args){BST bst = new BST();bst.Insert(50);bst.Insert(50);bst.Insert(30);bst.Insert(20);bst.Insert(40);bst.Insert(70);bst.Insert(60);bst.Insert(80);bst.LevelOrderTraversal();bst.DeleteNode(70);bst.LevelOrderTraversal();} }

好了，終于講完了二叉查找樹最基本的知識(shí)。這篇博客內(nèi)容很長(zhǎng)，如果第一遍沒(méi)讀懂，也沒(méi)關(guān)系，先休息一下，過(guò)段時(shí)間再讀一遍，可能就會(huì)更容易理解。

---

歡迎關(guān)注微信公眾號(hào) 萌一小棧

總結(jié)

以上是生活随笔為你收集整理的c# treeview查找并选中节点_最通俗易懂的二叉查找树(BST)详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。