算法系列15天速成第十二天树操作【中】-巨人网络通讯

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

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

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

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

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

一：线索二叉树

1 概念

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

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

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

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

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

2 结构图

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

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

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

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

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

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

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

3 基本操作

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

1> 线索二叉树结构

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

复制代码代码如下:

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

    #region 线索二叉树的结构
    /// summary>
/// 线索二叉树的结构
/// /summary>
/// typeparam name="T">/typeparam>
    public class ThreadTreeT>
    {
        public T data;
        public ThreadTreeT> left;
        public ThreadTreeT> 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_LDRT>(ref ThreadTreeT> tree, ref ThreadTreeT> 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 ThreadTreeT> BinTreeThreadNext_LDRT>(ThreadTreeT> 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 ThreadTreeT> BinTreeThreadPrev_LDRT>(ThreadTreeT> 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_LDRT>(ThreadTreeT> 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();

//生成根节点
ThreadTreestring> tree = CreateRoot();

//生成节点
AddNode(tree);

ThreadTreestring> prevNode = null;

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

            Console.WriteLine("\n线索二叉树的遍历结果为：\n");
            //中序遍历线索二叉树
            manager.BinTreeThread_LDR(tree);
        }

        #region 生成根节点
        /// summary>
/// 生成根节点
/// /summary>
/// returns>/returns>
        static ThreadTreestring> CreateRoot()
        {
            ThreadTreestring> tree = new ThreadTreestring>();

Console.WriteLine("请输入根节点，方便我们生成树\n");

tree.data = Console.ReadLine();

Console.WriteLine("根节点生成已经生成\n");

            return tree;
        }
        #endregion

        #region 插入节点操作
        /// summary>
/// 插入节点操作
/// /summary>
/// param name="tree">/param>
        static ThreadTreestring> AddNode(ThreadTreestring> tree)
        {
            ThreadTreeManager mananger = new ThreadTreeManager();

            while (true)
            {
                ThreadTreestring> node = new ThreadTreestring>();

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 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 ThreadTreeT> BinTreeThreadAddNodeT>(ThreadTreeT> tree, ThreadTreeT> 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

//先左子树遍历，寻找起始点
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;

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

            BinTreeThreadingCreate_LDR(ref tree.right, ref prevNode);
        }
        #endregion