【图解数据结构】二叉查找树

二叉查找树定义

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

二叉查找树节点定义

/// <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 + " ");
    }
}

插入节点

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

插入节点的整体流程:

  1. 把父节点设置为当前节点,即根节点。
  2. 如果新节点内的数据值小于当前节点内的数据值,那么把当前节点设置为当前节点的左子节点。如果新节点内的数据值大于当前节点内的数据值,那么就跳到步骤 4。
  3. 如果当前节点的左子节点的数值为空(null),就把新节点插入在这里并且退出循环。否则,跳到 while 循环的下一次循环操作中。
  4. 把当前节点设置为当前节点的右子节点。
  5. 如果当前节点的右子节点的数值为空(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;
}

查找特定值

根据二叉查找树的性质,从根结点开始,比较特定值和根结点值的大小。如果比根结点值大,则说明特定值在根结点右子树上,继续在右子节点执行此操作;如果比根结点值小,则说明特定值在根结点左子树上,继续在左子节点执行此操作。如果到执行完成都没有找到和特定值相等的节点值,那么二叉查找树中没有包含此特定值的节点。

代码实现:

/// <summary>
/// 查找二叉查找树特定值节点
/// </summary>
/// <param name="key">特定值</param>
/// <returns></returns>
public Node Find(int key)
{
    Node current = root;
    while (current.Data != key)
    {
        if (key < current.Data)
        {
            current = current.Left;
        }
        if (key > current.Data)
        {
            current = current.Right;
        }
        // 如果已到达 BST 的末尾
        if (current == null)
        {
            return null;
        }
    }
    return current;
}

删除节点

相对于前面的操作,二叉查找树的删除节点操作就显得要复杂一些了,因为删除节点会有破坏 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;
    }
}

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

当要删除的节点有一个子节点的时候,需要检查四个条件:

  1. 这个节点的子节点可能是左子节点;
  2. 这个节点的子节点可能是右子节点;
  3. 要删除的这个节点可能是左子节点;
  4. 要删除的这个节点可能是右子节点。

代码实现:

//要删除的结点是带有一个子节点的节点的处理
//首先判断子结点是左子节点还是右子节点,然后再判断当前节点是左子节点还是右子节点
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=nullsuccessor.Right=delNode.Right,节点40成为了节点38的右子节点。因为删除节点的后继节点一定是删除节点右子树的最左侧节点,所以后继节点肯定没有左子节点。删除节点被删除后,后继结点会补到删除节点的位置。 successor.Left=current.Left;,也就是删除节点的左子节点变成了后继节点的左子节点。

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

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

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

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

删除节点操作的整体流程:

  1. 把后继节点的右子节点赋值为后继节点的父节点的左子节点。
  2. 把要删除节点的右子节点赋值为后继节点的右子节点。
  3. 从父节点的右子节点中移除当前节点,并且把它指向后继节点。
  4. 从当前节点中移除当前节点的左子节点,并且把它指向后继节点的左子节点。

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

/// <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);
}

构造出的二叉查找树:

测试分三种情况:

测试删除叶子节点

删除叶子节点39

Console.Write("删除节点前: ");
bst.InOrder(bst.root);

bst.Delete(39);

Console.Write("删除节点后: ");
bst.InOrder(bst.root);

测试结果:

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

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

Console.Write("删除节点前: ");
bst.InOrder(bst.root);

bst.Delete(38);

Console.Write("删除节点后: ");
bst.InOrder(bst.root);

测试结果:

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

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

Console.Write("删除节点前: ");
bst.InOrder(bst.root);

bst.Delete(37);

Console.Write("删除节点后: ");
bst.InOrder(bst.root);

测试结果:


参考:

《数据结构与算法 C#语言描述》

《大话数据结构》

《数据结构与算法分析 C语言描述》

原文发布于微信公众号 - 撸码那些事(lumanxs)

原文发表时间:2018-06-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网杂技

今天由我亲自给大家总结

javascript内置对象有哪些? reg正则,booer,math,string,arr,obj,number,date,function,window全...

3198
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

43110
来自专栏爱撒谎的男孩

二叉树

1114
来自专栏企鹅号快讯

《常见排序算法》

1.概述 常见的排序算法,虽然很基础,但是很见功力,如果能思路清晰,很快写出来各个算法的代码实现,还是需要花一点功夫的,今天,就跟大家盘点下常用的一些算法。 冒...

1907
来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2178
来自专栏编程理解

数据结构(四):平衡二叉树(AVL树)

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

803
来自专栏Jack的Android之旅

疯狂java笔记之树和二叉树

树是一种非常常用的数据结构,树与前面介绍的线性表,栈,队列等线性结构不同,树是一种非线性结构

832
来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

2946
来自专栏我的技术专栏

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

954
来自专栏有趣的Python

算法与数据结构(五)二叉搜索树

二叉搜索树 (Binary Search Tree) 核心是解决问题。高效解决问题。 查找问题 Searching Problem: 查找问题是计算机中非常重...

2736

扫码关注云+社区