算法系列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 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
}

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

(0)

相关推荐

  • 算法系列15天速成 第十一天 树操作(上)

    先前我们讲的都是"线性结构",他的特征就是"一个节点最多有一个"前驱"和一个"后继".那么我们今天讲的树会是怎样的呢? 我们可以对"线性结构"改造一下,变为"一个节点最多有一个"前驱"和"多个后继".哈哈,这就是我们今天说的"树". 一: 树 我们思维中的"树"就是一种枝繁叶茂的形象,那么数据结构中的"树"该

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

    哈希查找: 对的,他就是哈希查找,说到哈希,大家肯定要提到哈希函数,呵呵,这东西已经在我们脑子里面形成固有思维了.大家一定要知道"哈希"中的对应关系.     比如说: "5"是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个"2",那么此时的"5"和"2"就建立一种对应关系,这种关系就是所谓的"哈希关系",在实际应用中也就形成了"2"是key,"5

  • 算法系列15天速成 第三天 七大经典排序【下】

    直接插入排序: 这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一手乱牌时,我们就要按照大小梳理扑克,30秒后, 扑克梳理完毕,4条3,5条s,哇塞......  回忆一下,俺们当时是怎么梳理的. 最左一张牌是3,第二张牌是5,第三张牌又是3,赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去, 第五张牌又是3,狂喜,哈哈,一门炮就这样产生了. 怎么样,生活中处处都是算法,早已经融入我们的生活和血液. 下面就上图说明:              看这张图不知道大家可

  • 算法系列15天速成 第二天 七大经典排序【中】

    首先感谢朋友们对第一篇文章的鼎力支持,感动中.......  今天说的是选择排序,包括"直接选择排序"和"堆排序". 话说上次"冒泡排序"被快排虐了,而且"快排"赢得了内库的重用,众兄弟自然眼红,非要找快排一比高下. 这不今天就来了两兄弟找快排算账. 1.直接选择排序: 先上图: 说实话,直接选择排序最类似于人的本能思想,比如把大小不一的玩具让三岁小毛孩对大小排个序, 那小孩首先会在这么多玩具中找到最小的放在第一位,然后找到次

  • 算法系列15天速成——第十三天 树操作【下】

    听说赫夫曼胜过了他的导师,被认为"青出于蓝而胜于蓝",这句话也是我比较欣赏的,嘻嘻. 一  概念 了解"赫夫曼树"之前,几个必须要知道的专业名词可要熟练记住啊. 1: 结点的权 "权"就相当于"重要度",我们形象的用一个具体的数字来表示,然后通过数字的大小来决定谁重要,谁不重要. 2: 路径 树中从"一个结点"到"另一个结点"之间的分支. 3: 路径长度 一个路径上的分支数量. 4: 树

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

    大家是否感觉到,树在数据结构中大行其道,什么领域都要沾一沾,碰一碰.就拿我们前几天学过的排序就用到了堆和今天讲的"二叉排序树",所以偏激的说,掌握的树你就是牛人了. 今天就聊聊这个"五大经典查找"中的最后一个"二叉排序树". 1. 概念:     <1> 其实很简单,若根节点有左子树,则左子树的所有节点都比根节点小.                             若根节点有右子树,则右子树的所有节点都比根节点大.     &

  • 算法系列15天速成 第一天 七大经典排序【上】

    针对现实中的排序问题,算法有七把利剑可以助你马道成功. 首先排序分为四种:       交换排序: 包括冒泡排序,快速排序.      选择排序: 包括直接选择排序,堆排序.      插入排序: 包括直接插入排序,希尔排序.      合并排序: 合并排序. 那么今天我们讲的就是交换排序,我们都知道,C#类库提供的排序是快排,为了让今天玩的有意思点,我们设计算法来跟类库提供的快排较量较量.争取KO对手. 冒泡排序: 首先我们自己来设计一下"冒泡排序",这种排序很现实的例子就是:我抓一

  • 算法系列15天速成——第十五天 图【下】(大结局)

    今天是大结局,说下"图"的最后一点东西,"最小生成树"和"最短路径". 一: 最小生成树 1. 概念 首先看如下图,不知道大家能总结点什么. 对于一个连通图G,如果其全部顶点和一部分边构成一个子图G1,当G1满足: ① 刚好将图中所有顶点连通.②顶点不存在回路.则称G1就是G的"生成树". 其实一句话总结就是:生成树是将原图的全部顶点以最小的边连通的子图,这不,如下的连通图可以得到下面的两个生成树. ② 对于一个带权的连通图,

  • 算法系列15天速成 第八天 线性表【下】

    一:线性表的简单回顾 上一篇跟大家聊过"线性表"顺序存储,通过实验,大家也知道,如果我每次向顺序表的头部插入元素,都会引起痉挛,效率比较低下,第二点我们用顺序存储时,容易受到长度的限制,反之就会造成空间资源的浪费. 二:链表 对于顺序表存在的若干问题,链表都给出了相应的解决方案. 1. 概念:其实链表的"每个节点"都包含一个"数据域"和"指针域". "数据域"中包含当前的数据. "指针域"

  • 算法系列15天速成 第十四天 图【上】

    今天来分享一下图,这是一种比较复杂的非线性数据结构,之所以复杂是因为他们的数据元素之间的关系是任意的,而不像树那样 被几个性质定理框住了,元素之间的关系还是比较明显的,图的使用范围很广的,比如网络爬虫,求最短路径等等,不过大家也不要胆怯, 越是复杂的东西越能体现我们码农的核心竞争力. 既然要学习图,得要遵守一下图的游戏规则. 一: 概念 图是由"顶点"的集合和"边"的集合组成.记作:G=(V,E): <1> 无向图 就是"图"中的边没

  • 算法系列15天速成 第十天 栈

    一: 概念 栈,同样是一种特殊的线性表,是一种Last In First Out(LIFO)的形式,现实中有很多这样的例子, 比如:食堂中的一叠盘子,我们只能从顶端一个一个的取. 二:存储结构 "栈"不像"队列",需要两个指针来维护,栈只需要一个指针就够了,这得益于栈是一种一端受限的线性表. 这里同样用"顺序结构"来存储这个"栈",top指针指向栈顶,所有的操作只能在top处. 代码段: 复制代码 代码如下: #region

  • 算法系列15天速成 第四天 五大经典查找【上】

    在我们的算法中,有一种叫做线性查找. 分为:顺序查找.        折半查找. 查找有两种形态: 分为:破坏性查找,   比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了. 哥不找23+的,所以此种查找破坏了原来的结构. 非破坏性查找, 这种就反之了,不破坏结构. 顺序查找: 这种非常简单,就是过一下数组,一个一个的比,找到为止. 复制代码 代码如下: using System;using System.Collections.

  • 算法系列15天速成 第九天 队列

    一:概念 队列是一个"先进先出"的线性表,牛X的名字就是"First in First Out(FIFO)",生活中有很多这样的场景,比如读书的时候去食堂打饭时的"排队".当然我们拒绝插队. 二:存储结构 前几天也说过,线性表有两种"存储结构",① 顺序存储,②链式存储.当然"队列"也脱离不了这两种服务,这里我就分享一下"顺序存储". 顺序存储时,我们会维护一个叫做"head头

  • 算法系列15天速成 第七天 线性表【上】

    哈哈,我们的数据也一样,存在这三种基本关系,用术语来说就是: <1>  线性关系.<2>  树形关系.<3>  网状关系. 一: 线性表 1 概念:                 线性表也就是关系户中最简单的一种关系,一对一.                  如:学生学号的集合就是一个线性表. 2 特征:                 ① 有且只有一个"首元素".                 ② 有且只有一个"末元素".

随机推荐