寫文章

首頁手記【圖解數(shù)據結構】二叉查找樹

【圖解數(shù)據結構】二叉查找樹

標簽：

深度學習

二叉查找树定义

每棵子树头节点的值都比各自左子树上所有节点值要大，也都比各自右子树上所有节点值要小。
二叉查找树的中序遍历序列一定是从小到大排列的。

二叉查找树节点定义

/// <summary>/// 二叉查找树节点/// </summary>public class Node{    /// <summary>
    /// 节点值
    /// </summary>
    public int Data { get; set; }    /// <summary>
    /// 左子节点
    /// </summary>
    public Node Left { get; set; }    /// <summary>
    /// 右子节点
    /// </summary>
    public Node Right { get; set; }    /// <summary>
    /// 打印节点值
    /// </summary>
    public void DisplayNode()    {
        Console.Write(Data + " ");
    }
}

插入节点

二叉查找树的插入节点操作相对比较简单，只需要找到要插入节点的位置放置即可。

插入节点的整体流程：
把父节点设置为当前节点，即根节点。
如果新节点内的数据值小于当前节点内的数据值，那么把当前节点设置为当前节点的左子节点。如果新节点内的数据值大于当前节点内的数据值，那么就跳到步骤 4。
如果当前节点的左子节点的数值为空（null），就把新节点插入在这里并且退出循环。否则，跳到 while 循环的下一次循环操作中。
把当前节点设置为当前节点的右子节点。
如果当前节点的右子节点的数值为空（null），就把新节点插入在这里并且退出循环。否则，跳到 while 循环的下一次循环操作中。

代码实现：

public class BinarySearchTree{    public Node root;    public BinarySearchTree()    {
        root = null;
    }    /// <summary>
    /// 二叉查找树插入结点
    /// </summary>
    /// <param name="i"></param>
    public void Insert(int i)    {
        Node newNode = new Node
        {
            Data = i
        };        if (root == null)
        {
            root = newNode;
        }        else
        {
            Node current = root;
            Node parent;            while (true)
            {
                parent = current;                if (i < current.Data)
                {
                    current = current.Left;                    if (current == null)
                    {
                        parent.Left = newNode;                        break;
                    }
                }                else
                {
                    current = current.Right;                    if (current == null)
                    {
                        parent.Right = newNode;                        break;
                    }
                }
            }
        }
    }
}

因为二叉查找树的中序遍历序列一定是由小到大排列的，所以我们可以通过中序遍历测试二叉查找树的插入操作。关于二叉树遍历操作可以移步我的上一篇博客【图解数据结构】二叉树遍历。

中序遍历代码实现：

/// <summary>/// 二叉查找树中序遍历/// </summary>/// <param name="node"></param>public void InOrder(Node node){    if (node != null)
    {
        InOrder(node.Left);
        node.DisplayNode();
        InOrder(node.Right);
    }
}

测试代码：

class BinarySearchTreeTest{    static void Main(string[] args)    {
        BinarySearchTree bst = new BinarySearchTree();
        bst.Insert(23);
        bst.Insert(45);
        bst.Insert(16);
        bst.Insert(37);
        bst.Insert(3);
        bst.Insert(99);
        bst.Insert(22);         

        Console.WriteLine("中序遍历: ");
        bst.InOrder(bst.root);

        Console.ReadKey();
    }
}

测试结果：

上面的测试代码形成了一棵这样的二叉查找树：

查找节点

对于二叉查找树（BST）有三件最容易做的事情：查找一个特殊数值，找到最小值，以及找到最大值。

查找最小值

根据二叉查找树的性质，二叉查找树的最小值一定是在左子树的最左侧子节点。

所以实现很简单，就是从根结点出发找出二叉查找树左子树的最左侧子节点。

代码实现：

/// <summary>/// 查找二叉查找树最小值/// </summary>/// <returns></returns>public int FindMin(){
    Node current = root;    while (current.Left != null)
    {
        current = current.Left;
    }    return current.Data;
}

查找最大值

根据二叉查找树的性质，二叉查找树的最大值一定是在右子树的最右侧子节点。

所以实现很简单，就是从根结点出发找出二叉查找树右子树的最右侧子节点。

代码实现：

/// <summary>/// 查找二叉查找树最大值/// </summary>/// <returns></returns>public int FindMax(){
    Node current = root;    while (current.Right != null)
    {
        current = current.Right;
    }    return current.Data;
}

查找特定值
删除节点
相对于前面的操作，二叉查找树的删除节点操作就显得要复杂一些了，因为删除节点会有破坏 BST 正确
层次顺序的风险。
我们都知道在二叉查找树中的结点可分为：没有子节点的节点，带有一个子节点的节点，带有两个子节点的节点。那么可以将二叉查找树的删除节点操作简单拆分一下，以便于我们的理解。如下图：

删除叶子节点

删除叶子节点是最简单的事情。唯一要做的就是把目标节点的父节点的一个子节点设置为空（null）。

查看这个节点的左子节点和右子节点是否为空（null）,都为空（null）说明为叶子节点。
然后检测这个节点是否是根节点。如果是，就把它设置为空（null）。
否则，如果isLeftChild 为true，把父节点的左子节点设置为空（null）；如果isLeftChild 为false,把父节点的右子节点设置为空（null）。

代码实现：

//要删除的结点是叶子结点的处理if (current.Left == null && current.Right == null)
{    if (current == root)
        root = null;    else if (isLeftChild)        parent.Left = null;    else
    {        parent.Right = null;
    }
}

删除带有一个子节点的节点

当要删除的节点有一个子节点的时候，需要检查四个条件：
这个节点的子节点可能是左子节点；
这个节点的子节点可能是右子节点；
要删除的这个节点可能是左子节点；
要删除的这个节点可能是右子节点。

代码实现：

//要删除的结点是带有一个子节点的节点的处理//首先判断子结点是左子节点还是右子节点，然后再判断当前节点是左子节点还是右子节点else if (current.Right == null)    if (current == root)
        root = current.Left;    else if (isLeftChild)        parent.Left = current.Left;    else
        parent.Right = current.Left;else if (current.Left == null)    if (current == root)
        root = current.Right;    else if (isLeftChild)        parent.Left = current.Right;    else
        parent.Right = current.Right;

删除带有两个子节点的节点

如果要删除标记为 52 的节点，需要重构这棵树。这里不能用起始节点为 54 的子树来替换它，因为 54 已经有一个左子节点了。这个问题的答案是把中序后继节点移动到要删除节点的位置上。当然还要区分后继节点本身是否有子节点。

这里我们需要了解一下后继节点的定义。

一个节点的后继节点是指，这个节点在中序遍历序列中的下一个节点。相应的，前驱节点是指这个节点在中序遍历序列中的上一个节点。

举个例子，下图中的二叉树中序遍历序列为: DBEAFCG，则A的后继节点为F，A的前驱节点为E。

了解了这些，删除带有两个子节点的节点的操作就可以转化为寻找要删除节点的后继节点并且把要删除节点的右子树赋给后继结点的右子节点，这里需要注意的是如果后继节点本身有子节点，则需要将后继节点的子结点赋给后继节点父节点的左子节点。

先上获取后继结点的代码，然后举个例子说明:

/// <summary>/// 获取后继结点/// </summary>/// <param name="delNode">要删除的结点</param>/// <returns></returns>public Node GetSuccessor(Node delNode){    //后继节点的父节点
    Node successorParent = delNode;    //后继节点
    Node successor = delNode.Right;
    Node current = delNode.Right.Left;    while (current != null)
    {
        successorParent = successor;
        successor = current;
        current = current.Left;
    }    //如果后继结点不是要删除结点的右子结点，
    //则要将后继节点的子结点赋给后继节点父节点的左节点
    //删除结点的右子结点赋给后继结点作为 后继结点的后继结点
    if (successor != delNode.Right)
    {
        successorParent.Left = successor.Right;
        successor.Right = delNode.Right;
    }    return successor;
}

删除带有两个子节点的节点的代码实现：

//要删除的结点是带有两个子节点的节点的处理else{
    Node successor = GetSuccessor(current);    if (current == root)
        root = successor;    else if (isLeftChild)        parent.Left = successor;    else
        parent.Right = successor;    //因为后继结点是要删除结点右子树的最左侧结点
    //所以后继结点的左子树肯定是要删除结点左子树
    successor.Left = current.Left;
}

我们观察到删除节点的后继节点一定是删除节点右子树的最左侧节点。这里有3种情况：

后继节点是删除节点的子节点

删除节点37，后继节点40是删除节点37的子节点。delNode是结点37，successor是节点40，delNode.Right是节点40，successor == delNode.Right,后继节点为删除节点的子节点,这种情况是最简单的。

后继节点不是删除节点的子节点

后继节点38是删除节点37右子树的最左侧节点。delNode是节点37，successor是节点38，successorParent 是节点40,delNode.Right 是节点40。successor != delNode.Right，所以要将 successorParent.Left = successor.Right;successor.Right = delNode.Right;。因为successor.Right==null,所以successorParent.Left = null。successor.Right = delNode.Right,节点40成为了节点38的右子节点。因为删除节点的后继节点一定是删除节点右子树的最左侧节点，所以后继节点肯定没有左子节点。删除节点被删除后，后继结点会补到删除节点的位置。successor.Left = current.Left;,也就是删除节点的左子节点变成了后继节点的左子节点。

完成删除节点后的搜索二叉树变为：

后继节点不是删除节点的子节点且有子节点

这种情况和上一种情况相似，唯一的区别是后继节点有子节点（注意肯定是右子节点）。也就是successorParent.Left = successor.Right;,后继节点的右子节点变成后继结点父节点的左子节点。因为successor.Right是节点39,所以节点40的左子节点变成了节点39。其它操作和上一种情况完全相同。

完成删除节点后的搜索二叉树变为：

删除节点操作的整体流程：
把后继节点的右子节点赋值为后继节点的父节点的左子节点。
把要删除节点的右子节点赋值为后继节点的右子节点。
从父节点的右子节点中移除当前节点，并且把它指向后继节点。
从当前节点中移除当前节点的左子节点，并且把它指向后继节点的左子节点。

综合以上删除节点的三种情况，删除节点操作的完整代码如下：

/// <summary>/// 二叉查找树删除节点/// </summary>/// <param name="key"></param>/// <returns></returns>public bool Delete(int key){    //要删除的当前结点
    Node current = root;    //当前结点的父结点
    Node parent = root;    //当前结点是否是左子树 
    bool isLeftChild = true;    //先通过二分查找找出要删除的结点
    while (current.Data != key)
    {
        parent = current;        if (key < current.Data)
        {
            isLeftChild = true;
            current = current.Left;
        }        else
        {
            isLeftChild = false;
            current = current.Right;
        }        if (current == null)            return false;
    }    //要删除的结点是叶子结点的处理
    if (current.Left == null && current.Right == null)
    {        if (current == root)
            root = null;        else if (isLeftChild)
            parent.Left = null;        else
        {
            parent.Right = null;
        }
    }    //要删除的结点是带有一个子节点的节点的处理
    else if (current.Right == null)        if (current == root)
            root = current.Left;        else if (isLeftChild)
            parent.Left = current.Left;        else
            parent.Right = current.Left;    else if (current.Left == null)        if (current == root)
            root = current.Right;        else if (isLeftChild)
            parent.Left = current.Right;        else
            parent.Right = current.Right;    //要删除的结点是带有两个子节点的节点的处理
    else
    {
        Node successor = GetSuccessor(current);        if (current == root)
            root = successor;        else if (isLeftChild)
            parent.Left = successor;        else
            parent.Right = successor;        //因为后继结点是要删除结点右子树的最左侧结点
        //所以后继结点的左子树肯定是要删除结点左子树
        successor.Left = current.Left;
    }    return true;
}/// <summary>/// 获取后继结点/// </summary>/// <param name="delNode">要删除的结点</param>/// <returns></returns>public Node GetSuccessor(Node delNode){    //后继节点的父节点
    Node successorParent = delNode;    //后继节点
    Node successor = delNode.Right;
    Node current = delNode.Right.Left;    while (current != null)
    {
        successorParent = successor;
        successor = current;
        current = current.Left;
    }    //如果后继结点不是要删除结点的右子结点，
    //则要将后继节点的子结点赋给后继节点父节点的左节点
    //删除结点的右子结点赋给后继结点作为 后继结点的后继结点
    if (successor != delNode.Right)
    {
        successorParent.Left = successor.Right;
        successor.Right = delNode.Right;
    }    return successor;
}

删除节点测试

我们还是使用中序遍历进行测试，首先构造二叉查找树：

static void Main(string[] args){
    BinarySearchTree bst = new BinarySearchTree();
    bst.Insert(23);
    bst.Insert(45);
    bst.Insert(16);
    bst.Insert(37);
    bst.Insert(3);
    bst.Insert(99);
    bst.Insert(22);
    bst.Insert(40);
    bst.Insert(35);
    bst.Insert(38);
    bst.Insert(44);
    bst.Insert(39);
}

构造出的二叉查找树：

测试分三种情况：

测试删除叶子节点
测试结果：
测试删除带有一个子节点的节点
测试结果：
测试删除带有两个子节点的节点
测试结果：
参考：
《数据结构与算法 C#语言描述》
《大话数据结构》
《数据结构与算法分析 C语言描述》
五一大家都出去happy了,为什么我还要自己在家撸代码，是因为爱吗？是因为责任吗？都不是。是因为我的心里只有学习（其实是因为穷）。哈哈，提前祝大家五一快乐，吃好玩好！
原文出处

點擊查看更多內容

為 TA 點贊

若覺得本文不錯，就分享一下吧！

評論

評論

共同學習，寫下你的評論

評論加載中...

展開查看更多評論

作者其他優(yōu)質文章

正在加載中

慕UI4062818

手記
篇

粉絲

97

獲贊與收藏

553

關注作者，訂閱最新文章

閱讀免費教程

后端通用面試教程

41個小節(jié) 32208 359

網絡編程入門教程

20個小節(jié) 13298 250

Pandas 入門教程

25個小節(jié) 19917 373

推薦

評論

收藏

共同學習，寫下你的評論



感謝您的支持，我會繼續(xù)努力的～

掃碼打賞，你說多少就多少

贊賞金額會直接到老師賬戶

支付方式

打開微信掃一掃，即可進行掃碼打賞哦

今天注冊有機會得

100積分直接送

付費專欄免費學

大額優(yōu)惠券免費領

立即參與放棄機會

點擊
抽獎

慕課手記新用戶專享福利

恭喜你，你的運氣太好了，居然抽中了 100個積分！

恭喜你，抽中了價值元的專欄！

太棒了，直接落到你賬戶里！

積分商城里的羅技鼠標、機械鍵盤、
Kindle 閱讀器、小米平衡車
Apple iPad （10.2英寸）、大額優(yōu)惠券
在等著你去兌換了噢

作者：

免費贈送

兌換碼：1111222211 復制

優(yōu)惠券可用于購買實戰(zhàn)課、體系課
無門檻使用

先去看看，有什么好東西馬上兌換我愛學習，選課去


第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

熱搜

最近搜索清空

【圖解數(shù)據結構】二叉查找樹

二叉查找树定义

二叉查找树节点定义

插入节点

查找节点

查找最小值

查找最大值

删除节点

删除叶子节点

删除带有一个子节点的节点

删除带有两个子节点的节点

后继节点是删除节点的子节点

后继节点不是删除节点的子节点

后继节点不是删除节点的子节点且有子节点

删除节点测试

閱讀免費教程