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

return leftNode;
            }
        }
        #endregion

<5> 遍历线索二叉树

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

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

复制代码 代码如下:

#region 遍历线索二叉树
        /// <summary>
/// 遍历线索二叉树
/// </summary>
/// <typeparam></typeparam>
/// <param></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></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 退出");

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!