欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法系列15天速成 第十二天 树操作【中】

程序员文章站 2022-05-14 15:00:32
先前说了树的基本操作,我们采用的是二叉链表来保存树形结构,当然二叉有二叉的困扰之处,比如我想找到当前结点的“前驱”和“后继”,那么我们就必须要遍历一下树,然后才能定位到该“...

先前说了树的基本操作,我们采用的是二叉链表来保存树形结构,当然二叉有二叉的困扰之处,比如我想找到当前结点的“前驱”和“后继”,那么我们就必须要遍历一下树,然后才能定位到该“节点”的“前驱”和“后继”,每次定位都是o(n),这不是我们想看到的,那么有什么办法来解决呢?

   (1) 在节点域中增加二个指针域,分别保存“前驱”和“后继”,那么就是四叉链表了,哈哈,还是有点浪费空间啊。

   (2) 看下面的这个二叉树,我们知道每个结点有2个指针域,4个节点就有8个指针域,其实真正保存节点的指针

            仅有3个,还有5个是空闲的,那么为什么我们不用那些空闲的指针域呢,达到资源的合理充分的利用。

算法系列15天速成 第十二天 树操作【中】

一: 线索二叉树

1  概念

      刚才所说的在空闲的指针域里面存放“前驱”和“后继”就是所谓的线索。

        <1>  左线索:   在空闲的左指针域中存放该“结点”的“前驱”被认为是左线索。

        <2>  右线索:   在空闲的右指针域中存放该“结点“的”后继“被认为是右线索。

      当“二叉链表”被套上这种线索,就被认为是线索链表,当“二叉树”被套上这种线索就被认为是线索二叉树,当然线索根据

二叉树的遍历形式不同被分为“先序线索”,“中序线索”,“后序线索”。

2  结构图

      说了这么多,我们还是上图说话,就拿下面的二叉树,我们构建一个中序线索二叉树,需要多动动脑子哟。

     <1> 首先要找到“中序遍历”中的首结点d,因为“d结点”是首节点,所以不存在“前驱”,左指针自然是空,

            ”d节点”的右指针存放的是“后继”,那么根据“中序遍历”的规则应该是b,所以d的右指针存放着b节点。

     <2>  接着就是“b节点”,他的左指针不为空,所以就不管了,但是他的“右指针”空闲,根据规则“b结点“的右

    指针存放的是"a结点“。

     <3>  然后就是“a节点”,他已经被塞的满满的,所以就没有“线索”可言了。

     <4>  最后就是“c节点”,根据规则,他的“左指针”存放着就是“a节点“,”c节点“是最后一个节点,右指针自然就是空的,你懂的。

算法系列15天速成 第十二天 树操作【中】

3 基本操作   

   常用的操作一般有“创建线索二叉树”,”查找后继节点“,”查找前驱节点“,”遍历线索二叉树“,下面的操作我们就以”中序遍历“来创建中序线索二叉树。

<1>  线索二叉树结构

          从“结构图”中可以看到,现在结点的指针域中要么是”子节点(subtree)“或者是”线索(thread)“,此时就要设立标志位来表示指针域存放的是哪一种。

复制代码 代码如下:

#region 节点标识(用于判断孩子是节点还是线索)
    /// <summary>
/// 节点标识(用于判断孩子是节点还是线索)
/// </summary>
    public enum nodeflag
    {
        subtree = 1,
        thread = 2
    }
    #endregion

    #region 线索二叉树的结构
    /// <summary>
/// 线索二叉树的结构
/// </summary>
/// <typeparam name="t"></typeparam>
    public class threadtree<t>
    {
        public t data;
        public threadtree<t> left;
        public threadtree<t> right;
        public nodeflag leftflag;
        public nodeflag rightflag;
    }
    #endregion

<2>  创建线索二叉树

        刚才也说了如何构建中序线索二叉树,在代码实现中,我们需要定义一个节点来保存当前节点的前驱,我练习的时候迫不得已,只能使用两个

    ref来实现地址操作,达到一个tree能够让两个变量来操作。

复制代码 代码如下:

#region 中序遍历构建线索二叉树
        /// <summary>
/// 中序遍历构建线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public void bintreethreadingcreate_ldr<t>(ref threadtree<t> tree, ref threadtree<t> prevnode)
        {
            if (tree == null)
                return;

            //先左子树遍历,寻找起始点
            bintreethreadingcreate_ldr(ref tree.left, ref prevnode);

            //如果left为空,则说明该节点可以放“线索”
            tree.leftflag = (tree.left == null) ? nodeflag.thread : nodeflag.subtree;

            //如果right为空,则说明该节点可以放“线索”
            tree.rightflag = (tree.right == null) ? nodeflag.thread : nodeflag.subtree;

            if (prevnode != null)
            {
                if (tree.leftflag == nodeflag.thread)
                    tree.left = prevnode;
                if (prevnode.rightflag == nodeflag.thread)
                    prevnode.right = tree;
            }

            //保存前驱节点
            prevnode = tree;

            bintreethreadingcreate_ldr(ref tree.right, ref prevnode);
        }
        #endregion

<3> 查找后继结点

         现在大家都知道,后继结点都是保存在“结点“的右指针域中,那么就存在”两种情况“。

            《1》 拿“b节点“来说,他没有右孩子,则肯定存放着线索(thread),所以我们直接o(1)的返回他的线索即可。

            《2》 拿“a节点”来说,他有右孩子,即右指针域存放的是subtree,悲哀啊,如何才能得到“a节点“的后继呢?其实也很简单,

根据”中序“的定义,”a节点“的后继必定是”a节点“的右子树往左链找的第一个没有左孩子的节点(只可意会,不可言传,嘻嘻)。

复制代码 代码如下:

#region 查找指定节点的后继
        /// <summary>
/// 查找指定节点的后继
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public threadtree<t> bintreethreadnext_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return null;

            //如果查找节点的标志域中是thread,则直接获取
            if (tree.rightflag == nodeflag.thread)
                return tree.right;
            else
            {
                //根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
                var rightnode = tree.right;

                //如果该节点是subtree就需要循环遍历
                while (rightnode.leftflag == nodeflag.subtree)
                {
                    rightnode = rightnode.left;
                }
                return rightnode;
            }
        }
        #endregion

<4> 查找前驱节点
       

        这个跟(3)的操作很类似,同样也具有两个情况。

          《1》  拿“c结点”来说,他没有“左子树”,则说明“c节点”的左指针为thread,此时,我们只要返回左指针域即可得到前驱结点。

          《2》  拿"a节点“来说,他有”左子树“,则说明”a节点“的左指针为subtree,那么怎么找的到”a节点“的前驱呢?同样啊,根据

                   ”中序遍历“的性质,我们可以得知在”a节点“的左子树中往”右链“中找到第一个没有”右孩子“的节点。

复制代码 代码如下:

#region 查找指定节点的前驱
        /// <summary>
/// 查找指定节点的前驱
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <returns></returns>
        public threadtree<t> bintreethreadprev_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return null;

            //如果标志域中存放的是线索,那么可以直接找出来
            if (tree.leftflag == nodeflag.thread)
                return tree.left;
            else
            {
                //根据”中序“的规则可知,如果不为thread,则要找出左子树的最后节点
//也就是左子树中最后输出的元素
                var leftnode = tree.left;

                while (leftnode.rightflag == nodeflag.subtree)
                    leftnode = leftnode.right;

                return leftnode;
            }
        }
        #endregion

<5> 遍历线索二叉树

          因为我们构建线索的时候采用的是“中序”,那么我们遍历同样采用“中序”,大家是否看到了“线索”的好处,此时我们找某个节点的时间复杂度变为了

        o(1) ~0(n)的时间段,比不是线索的时候查找“前驱"和“后继”效率要高很多。

复制代码 代码如下:

#region 遍历线索二叉树
        /// <summary>
/// 遍历线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public void bintreethread_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return;

            while (tree.leftflag == nodeflag.subtree)
                tree = tree.left;

            do
            {
                console.write(tree.data + "\t");

                tree = bintreethreadnext_ldr(tree);

            } while (tree != null);

        }
        #endregion

最后上一下总的运行代码

复制代码 代码如下:

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

namespace threadchaintree
{
    class program
    {
        static void main(string[] args)
        {
            threadtreemanager manager = new threadtreemanager();

            //生成根节点
            threadtree<string> tree = createroot();

            //生成节点
            addnode(tree);

            threadtree<string> prevnode = null;

            //构建线索二叉树
            manager.bintreethreadingcreate_ldr(ref tree, ref prevnode);

            console.writeline("\n线索二叉树的遍历结果为:\n");
            //中序遍历线索二叉树
            manager.bintreethread_ldr(tree);
        }

        #region 生成根节点
        /// <summary>
/// 生成根节点
/// </summary>
/// <returns></returns>
        static threadtree<string> createroot()
        {
            threadtree<string> tree = new threadtree<string>();

            console.writeline("请输入根节点,方便我们生成树\n");

            tree.data = console.readline();

            console.writeline("根节点生成已经生成\n");

            return tree;
        }
        #endregion

        #region 插入节点操作
        /// <summary>
/// 插入节点操作
/// </summary>
/// <param name="tree"></param>
        static threadtree<string> addnode(threadtree<string> tree)
        {
            threadtreemanager mananger = new threadtreemanager();

            while (true)
            {
                threadtree<string> node = new threadtree<string>();

                console.writeline("请输入要插入节点的数据:\n");

                node.data = console.readline();

                console.writeline("请输入要查找的父节点数据:\n");

                var parentdata = console.readline();

                if (tree == null)
                {
                    console.writeline("未找到您输入的父节点,请重新输入。");
                    continue;
                }

                console.writeline("请确定要插入到父节点的:1 左侧,2 右侧");

                direction direction = (direction)enum.parse(typeof(direction), console.readline());

                tree = mananger.bintreethreadaddnode(tree, node, parentdata, direction);

                console.writeline("插入成功,是否继续?  1 继续, 2 退出");

                if (int.parse(console.readline()) == 1)
                    continue;
                else
                    break;
            }

            return tree;
        }
        #endregion
    }

    #region 节点标识(用于判断孩子是节点还是线索)
    /// <summary>
/// 节点标识(用于判断孩子是节点还是线索)
/// </summary>
    public enum nodeflag
    {
        subtree = 1,
        thread = 2
    }
    #endregion

    #region 线索二叉树的结构
    /// <summary>
/// 线索二叉树的结构
/// </summary>
/// <typeparam name="t"></typeparam>
    public class threadtree<t>
    {
        public t data;
        public threadtree<t> left;
        public threadtree<t> right;
        public nodeflag leftflag;
        public nodeflag rightflag;
    }
    #endregion

    #region 插入左节点或者右节点
    /// <summary>
/// 插入左节点或者右节点
/// </summary>
    public enum direction { left = 1, right = 2 }
    #endregion

    #region 线索二叉树的基本操作
    /// <summary>
/// 线索二叉树的基本操作
/// </summary>
    public class threadtreemanager
    {
        #region 将指定节点插入到二叉树中
        /// <summary>
/// 将指定节点插入到二叉树中
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <param name="node"></param>
/// <param name="direction">插入做左是右</param>
/// <returns></returns>
        public threadtree<t> bintreethreadaddnode<t>(threadtree<t> tree, threadtree<t> node, t data, direction direction)
        {
            if (tree == null)
                return null;

            if (tree.data.equals(data))
            {
                switch (direction)
                {
                    case direction.left:
                        if (tree.left != null)
                            throw new exception("树的左节点不为空,不能插入");
                        else
                            tree.left = node;

                        break;
                    case direction.right:
                        if (tree.right != null)
                            throw new exception("树的右节点不为空,不能插入");
                        else
                            tree.right = node;

                        break;
                }
            }

            bintreethreadaddnode(tree.left, node, data, direction);
            bintreethreadaddnode(tree.right, node, data, direction);

            return tree;
        }
        #endregion

        #region 中序遍历构建线索二叉树
        /// <summary>
/// 中序遍历构建线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public void bintreethreadingcreate_ldr<t>(ref threadtree<t> tree, ref threadtree<t> prevnode)
        {
            if (tree == null)
                return;

            //先左子树遍历,寻找起始点
            bintreethreadingcreate_ldr(ref tree.left, ref prevnode);

            //如果left为空,则说明该节点可以放“线索”
            tree.leftflag = (tree.left == null) ? nodeflag.thread : nodeflag.subtree;

            //如果right为空,则说明该节点可以放“线索”
            tree.rightflag = (tree.right == null) ? nodeflag.thread : nodeflag.subtree;

            if (prevnode != null)
            {
                if (tree.leftflag == nodeflag.thread)
                    tree.left = prevnode;
                if (prevnode.rightflag == nodeflag.thread)
                    prevnode.right = tree;
            }

            //保存前驱节点
            prevnode = tree;

            bintreethreadingcreate_ldr(ref tree.right, ref prevnode);
        }
        #endregion

        #region 查找指定节点的后继
        /// <summary>
/// 查找指定节点的后继
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public threadtree<t> bintreethreadnext_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return null;

            //如果查找节点的标志域中是thread,则直接获取
            if (tree.rightflag == nodeflag.thread)
                return tree.right;
            else
            {
                //根据中序遍历的规则是寻找右子树中中序遍历的第一个节点
                var rightnode = tree.right;

                //如果该节点是subtree就需要循环遍历
                while (rightnode.leftflag == nodeflag.subtree)
                {
                    rightnode = rightnode.left;
                }
                return rightnode;
            }
        }
        #endregion

        #region 查找指定节点的前驱
        /// <summary>
/// 查找指定节点的前驱
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <returns></returns>
        public threadtree<t> bintreethreadprev_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return null;

            //如果标志域中存放的是线索,那么可以直接找出来
            if (tree.leftflag == nodeflag.thread)
                return tree.left;
            else
            {
                //根据”中序“的规则可知,如果不为thread,则要找出左子树的最后节点
//也就是左子树中最后输出的元素
                var leftnode = tree.left;

                while (leftnode.rightflag == nodeflag.subtree)
                    leftnode = leftnode.right;

                return leftnode;
            }
        }
        #endregion

        #region 遍历线索二叉树
        /// <summary>
/// 遍历线索二叉树
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public void bintreethread_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return;

            while (tree.leftflag == nodeflag.subtree)
                tree = tree.left;

            do
            {
                console.write(tree.data + "\t");

                tree = bintreethreadnext_ldr(tree);

            } while (tree != null);

        }
        #endregion
    }
    #endregion
}

将文章开头处的数据输入到存储结构中

算法系列15天速成 第十二天 树操作【中】