服务器之家

服务器之家 > 正文

算法系列15天速成 第六天 五大经典查找【下】

时间:2020-07-26 17:33     来源/作者:编程技术网

大家是否感觉到,树在数据结构中大行其道,什么领域都要沾一沾,碰一碰。
就拿我们前几天学过的排序就用到了堆和今天讲的”二叉排序树“,所以偏激的说,掌握的树你就是牛人了。

今天就聊聊这个”五大经典查找“中的最后一个”二叉排序树“。

1. 概念:
     <1> 其实很简单,若根节点有左子树,则左子树的所有节点都比根节点小。
                             若根节点有右子树,则右子树的所有节点都比根节点大。
     <2> 如图就是一个”二叉排序树“,然后对照概念一比较比较。

         算法系列15天速成 第六天 五大经典查找【下】

2.实际操作:

    我们都知道,对一个东西进行操作,无非就是增删查改,接下来我们就聊聊其中的基本操作。

    <1> 插入:相信大家对“排序树”的概念都清楚了吧,那么插入的原理就很简单了。

                    比如说我们插入一个20到这棵树中。

                                 首先:20跟50比,发现20是老小,不得已,得要归结到50的左子树中去比较。

                                 然后:20跟30比,发现20还是老小。

                              再然后:20跟10比,发现自己是老大,随即插入到10的右子树中。

                                 最后: 效果呈现图如下:

               

               算法系列15天速成 第六天 五大经典查找【下】

    <2>查找:相信懂得了插入,查找就跟容易理解了。

                    就拿上面一幅图来说,比如我想找到节点10.

                                     首先:10跟50比,发现10是老小,则在50的左子树中找。

                                     然后:10跟30比,发现还是老小,则在30的左子树中找。

                                  再然后:  10跟10比,发现一样,然后就返回找到的信号。

                

     <3>删除:删除节点在树中还是比较麻烦的,主要有三种情况。

                   《1》 删除的是“叶节点20“,这种情况还是比较简单的,删除20不会破坏树的结构。如图:

                    

                      算法系列15天速成 第六天 五大经典查找【下】

                   《2》删除”单孩子节点90“,这个情况相比第一种要麻烦一点点,需要把他的孩子顶上去。

                    

                       算法系列15天速成 第六天 五大经典查找【下】

                   《3》删除“左右孩子都有的节点50”,这个让我在代码编写上纠结了好长时间,问题很直白,

                           我把50删掉了,谁顶上去了问题,是左孩子呢?还是右孩子呢?还是另有蹊跷?这里我就

                           坦白吧,不知道大家可否知道“二叉树”的中序遍历,不过这个我会在后面讲的,现在可以当

                          公式记住吧,就是找到右节点的左子树最左孩子。

                          比如:首先 找到50的右孩子70。

                                  然后  找到70的最左孩子,发现没有,则返回自己。

                                  最后  原始图和最终图如下。 

 算法系列15天速成 第六天 五大经典查找【下】 算法系列15天速成 第六天 五大经典查找【下】

 

3.说了这么多,上代码说话。

 

复制代码 代码如下:


using system;
using system.collections.generic;
using system.linq;
using system.text;
using system.diagnostics;

 

namespace treesearch
{
    class program
    {
        static void main(string[] args)
        {
            list<int> list = new list<int>() { 50, 30, 70, 10, 40, 90, 80 };

            //创建二叉遍历树
            bstree bstree = createbst(list);

            console.write("中序遍历的原始数据:");

            //中序遍历
            ldr_bst(bstree);

            console.writeline("\n---------------------------------------------------------------------------n");

            //查找一个节点
            console.writeline("\n10在二叉树中是否包含:" + searchbst(bstree, 10));

            console.writeline("\n---------------------------------------------------------------------------n");

            bool isexcute = false;

            //插入一个节点
            insertbst(bstree, 20, ref isexcute);

            console.writeline("\n20插入到二叉树,中序遍历后:");

            //中序遍历
            ldr_bst(bstree);

            console.writeline("\n---------------------------------------------------------------------------n");

            console.write("删除叶子节点 20, \n中序遍历后:");

            //删除一个节点(叶子节点)
            deletebst(ref bstree, 20);

            //再次中序遍历
            ldr_bst(bstree);

            console.writeline("\n****************************************************************************\n");

            console.writeline("删除单孩子节点 90, \n中序遍历后:");

            //删除单孩子节点
            deletebst(ref bstree, 90);

            //再次中序遍历
            ldr_bst(bstree);

            console.writeline("\n****************************************************************************\n");

            console.writeline("删除根节点 50, \n中序遍历后:");
            //删除根节点
            deletebst(ref bstree, 50);

            ldr_bst(bstree);

        }

        ///<summary>
/// 定义一个二叉排序树结构
///</summary>
        public class bstree
        {
            public int data;
            public bstree left;
            public bstree right;
        }

        ///<summary>
/// 二叉排序树的插入操作
///</summary>
///<param name="bstree">排序树</param>
///<param name="key">插入数</param>
///<param name="isexcute">是否执行了if语句</param>
        static void insertbst(bstree bstree, int key, ref bool isexcute)
        {
            if (bstree == null)
                return;

            //如果父节点大于key,则遍历左子树
            if (bstree.data > key)
                insertbst(bstree.left, key, ref isexcute);
            else
                insertbst(bstree.right, key, ref isexcute);

            if (!isexcute)
            {
                //构建当前节点
                bstree current = new bstree()
                  {
                      data = key,
                      left = null,
                      right = null
                  };

                //插入到父节点的当前元素
                if (bstree.data > key)
                    bstree.left = current;
                else
                    bstree.right = current;

                isexcute = true;
            }

        }

        ///<summary>
/// 创建二叉排序树
///</summary>
///<param name="list"></param>
        static bstree createbst(list<int> list)
        {
            //构建bst中的根节点
            bstree bstree = new bstree()
            {
                data = list[0],
                left = null,
                right = null
            };

            for (int i = 1; i < list.count; i++)
            {
                bool isexcute = false;
                insertbst(bstree, list[i], ref isexcute);
            }
            return bstree;
        }

        ///<summary>
/// 在排序二叉树中搜索指定节点
///</summary>
///<param name="bstree"></param>
///<param name="key"></param>
///<returns></returns>
        static bool searchbst(bstree bstree, int key)
        {
            //如果bstree为空,说明已经遍历到头了
            if (bstree == null)
                return false;

            if (bstree.data == key)
                return true;

            if (bstree.data > key)
                return searchbst(bstree.left, key);
            else
                return searchbst(bstree.right, key);
        }

        ///<summary>
/// 中序遍历二叉排序树
///</summary>
///<param name="bstree"></param>
///<returns></returns>
        static void ldr_bst(bstree bstree)
        {
            if (bstree != null)
            {
                //遍历左子树
                ldr_bst(bstree.left);

                //输入节点数据
                console.write(bstree.data + "");

                //遍历右子树
                ldr_bst(bstree.right);
            }
        }

        ///<summary>
/// 删除二叉排序树中指定key节点
///</summary>
///<param name="bstree"></param>
///<param name="key"></param>
        static void deletebst(ref bstree bstree, int key)
        {
            if (bstree == null)
                return;

            if (bstree.data == key)
            {
                //第一种情况:叶子节点
                if (bstree.left == null && bstree.right == null)
                {
                    bstree = null;
                    return;
                }
                //第二种情况:左子树不为空
                if (bstree.left != null && bstree.right == null)
                {
                    bstree = bstree.left;
                    return;
                }
                //第三种情况,右子树不为空
                if (bstree.left == null && bstree.right != null)
                {
                    bstree = bstree.right;
                    return;
                }
                //第四种情况,左右子树都不为空
                if (bstree.left != null && bstree.right != null)
                {
                    var node = bstree.right;

                    //找到右子树中的最左节点
                    while (node.left != null)
                    {
                        //遍历它的左子树
                        node = node.left;
                    }

                    //交换左右孩子
                    node.left = bstree.left;

                    //判断是真正的叶子节点还是空左孩子的父节点
                    if (node.right == null)
                    {
                        //删除掉右子树最左节点
                        deletebst(ref bstree, node.data);

                        node.right = bstree.right;
                    }
                    //重新赋值一下
                    bstree = node;

                }
            }

            if (bstree.data > key)
            {
                deletebst(ref bstree.left, key);
            }
            else
            {
                deletebst(ref bstree.right, key);
            }
        }
    }
}

 

运行结果:

算法系列15天速成 第六天 五大经典查找【下】

值的注意的是:二叉排序树同样采用“空间换时间”的做法。

突然发现,二叉排序树的中序遍历同样可以排序数组,呵呵,不错!

ps:  插入操作:o(logn)。
       删除操作:o(logn)。
       查找操作:o(logn)。

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
沙雕群名称大全2019精选 今年最火的微信群名沙雕有创意
沙雕群名称大全2019精选 今年最火的微信群名沙雕有创意 2019-07-07
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
返回顶部