加载中...

第十一天 树操作【上】

先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“。那么我们今天讲的树会是怎样的呢？

我们可以对”线性结构“改造一下，变为”一个节点最多有一个"前驱“和”多个后继“。哈哈，这就是我们今天说的”树“。

 

一： 树

      我们思维中的”树“就是一种枝繁叶茂的形象，那么数据结构中的”树“该是怎么样呢？对的，他是一种现实中倒立的树。

1：术语

     其实树中有很多术语的，这个是我们学习树形结构必须掌握的。

     <1>  父节点，子节点，兄弟节点

                  这个就比较简单了，B和C的父节点就是A，反过来说就是B和C是A的子节点。B和C就是兄弟节点。

     <2>  结点的度

                 其实”度“就是”分支数“，比如A的分支数有两个“B和C",那么A的度为2。

     <3> 树的度

                看似比较莫名其妙吧，他和”结点的度“的区别就是，树的度讲究大局观，乃树中最大的结点度，其实也就是2。

     <4> 叶结点，分支结点

                叶结点就是既没有左孩子也没有右孩子结点，也就是结点度为0。分支节点也就是if的else的条件咯。

    <5> 结点的层数

               这个很简单，也就是树有几层。

   <6> 有序树，无序树

               有序树我们先前也用过，比如“堆”和“二叉排序树”，说明这种树是按照一定的规则进行排序的，else条件就是无序树。

   <7>  森林

               现实中，很多的树形成了森林，那在数据结构中，我们把上图的“A”节点砍掉，那么B，C子树合一起就是森林咯。

 

2: 树的表示

     树这个结构的表示其实有很多种，常用的也就是“括号”表示法。

     比如上面的树就可以表示为：(A(B(D),(E)),(C(F),(G)))

 

二： 二叉树

         在我们项目开发中，很多地方都会用到树，但是多叉树的处理还是比较纠结的，所以俺们本着“大事化小，小事化了“的原则

      把”多叉树“转化为”二叉树“，那么问题就简化了很多。

 

1： ”二叉树“和”树“有什么差异呢？

         第一点:  树的度没有限制，而“二叉树”最多只能有两个，不然也就不叫二叉树了，哈哈。

         第二点：树中的子树没有左右划分，很简单啊，找不到参照点，二叉树就有参照物咯。

 

2： 二叉树的类型

       二叉树中有两种比较完美的类型，“完全二叉树”和“满二叉树”。

          <1>  满二叉树    

                       除叶子节点外，所有节点的度都为2，文章开头处的树就是这里的“满二叉树”。

          <2>  完全二叉树

                      必须要满足两个条件就即可：  干掉最后一层，二叉树变为“满二叉树”。

                                                              最后一层的叶节点必须是“从左到右”依次排开。

                     我们干掉文章开头处的节点“F和”G",此时还是“完全二叉树”，但已经不是“满二叉树”了，你懂的。

 

3： 二叉树的性质

         二叉树中有5点性质非常重要，也是俺们必须要记住的。

     <1>  二叉树中，第i层的节点最多有2(i-1)个。

     <2>  深度为k的二叉树最多有2k-1个节点。

     <3>  二叉树中，叶子节点树为N1个，度为2的节点有N2个，那么N1=N2+1。

     <4>  具有N个结点的二叉树深度为（Log2 N）+1层。

     <5>  N个结点的完全二叉树如何用顺序存储，对于其中的一个结点i，存在以下关系，

              2*i是结点i的父结点。

              i/2是结点i的左孩子。

              (i/2)+1是结点i的右孩子。

 

4： 二叉树的顺序存储

      同样的存储方式也有两种，“顺序存储”和“链式存储”。

       <1> 顺序存储

                 说实话，树的存储用顺序结构比较少，因为从性质定理中我们都可以看出只限定为“完全二叉树”，那么如果二叉树不是

              “完全二叉树”，那我们就麻烦了，必须将其转化为“完全二叉树”，将空的节点可以用“#”代替，图中也可看出，为了维护

              性质定理5的要求，我们牺牲了两个”资源“的空间。

     <2> 链式存储

               上面也说了，顺序存储会造成资源的浪费，所以嘛，我们开发中用的比较多的还是“链式存储”，同样“链式存储”

            也非常的形象，非常的合理。

               一个结点存放着一个“左指针”和一个“右指针”，这就是二叉链表。

               如何方便的查找到该结点的父结点，可以采用三叉链表。

 

5: 常用操作

      一般也就是“添加结点“，“查找节点”，“计算深度”，“遍历结点”，“清空结点”

   

<1> 二叉链表来定义链式存储模型 

  1. #region 二叉链表存储结构
  2.     /// <summary>
  3. /// 二叉链表存储结构
  4. /// </summary>
  5. /// <typeparam name="T"></typeparam>
  6.     public class ChainTree<T>
  7.     {
  8.         public T data;
  9.  
  10.         public ChainTree<T> left;
  11.  
  12.         public ChainTree<T> right; 
  13.     }
  14.     #endregion

<2> 添加结点

             要添加结点，我们就要找到添加结点的父结点，并且根据指示插入到父结点中指定左结点或者右结点。 

  1. #region 将指定节点插入到二叉树中
  2.         /// <summary>
  3. /// 将指定节点插入到二叉树中
  4. /// </summary>
  5. /// <typeparam name="T"></typeparam>
  6. /// <param name="tree"></param>
  7. /// <param name="node"></param>
  8. /// <param name="direction">插入做左是右</param>
  9. /// <returns></returns>
  10.         public ChainTree<T> BinTreeAddNode<T>(ChainTree<T> tree, ChainTree<T> node, T data, Direction direction)
  11.         {
  12.             if (tree == null)
  13.                 return null;
  14.  
  15.             if (tree.data.Equals(data))
  16.             {
  17.                 switch (direction)
  18.                 {
  19.                     case Direction.Left:
  20.                         if (tree.left != null)
  21.                             throw new Exception("树的左节点不为空，不能插入");
  22.                         else
  23.                             tree.left = node;
  24.  
  25.                         break;
  26.                     case Direction.Right:
  27.                         if (tree.right != null)
  28.                             throw new Exception("树的右节点不为空，不能插入");
  29.                         else
  30.                             tree.right = node;
  31.  
  32.                         break;
  33.                 }
  34.             }
  35.  
  36.             BinTreeAddNode(tree.left, node, data, direction);
  37.             BinTreeAddNode(tree.right, node, data, direction);
  38.  
  39.             return tree;
  40.         }
  41.         #endregion

<3>  查找节点  

                 二叉树中到处都散发着递归思想，很能锻炼一下我们对递归的认识，同样查找也是用到了递归思想。 

  1. #region 在二叉树中查找指定的key
  2.         /// <summary>
  3. ///在二叉树中查找指定的key
  4. /// </summary>
  5. /// <typeparam name="T"></typeparam>
  6. /// <param name="tree"></param>
  7. /// <param name="data"></param>
  8. /// <returns></returns>
  9.         public ChainTree<T> BinTreeFind<T>(ChainTree<T> tree, T data)
  10.         {
  11.             if (tree == null)
  12.                 return null;
  13.  
  14.             if (tree.data.Equals(data))
  15.                 return tree;
  16.  
  17.             return BinTreeFind(tree, data);
  18.         }
  19.         #endregion

<4> 计算深度

          这个问题纠结了我二个多小时，原因在于没有深刻的体会到递归，其实主要思想就是递归左子树和右子树，然后得出较大的一个。 

  1. #region 获取二叉树的深度
  2.         /// <summary>
  3. /// 获取二叉树的深度
  4. /// </summary>
  5. /// <typeparam name="T"></typeparam>
  6. /// <param name="tree"></param>
  7. /// <returns></returns>
  8.         public int BinTreeLen<T>(ChainTree<T> tree)
  9.         {
  10.             int leftLength;
  11.             int rightLength;
  12.  
  13.             if (tree == null)
  14.                 return 0;
  15.  
  16.             //递归左子树的深度
  17.             leftLength = BinTreeLen(tree.left);
  18.  
  19.             //递归右子书的深度
  20.             rightLength = BinTreeLen(tree.right);
  21.  
  22.             if (leftLength > rightLength)
  23.                 return leftLength + 1;
  24.             else
  25.                 return rightLength + 1;
  26.         }
  27.         #endregion

<5>  遍历结点

             二叉树中遍历节点的方法还是比较多的，有“先序”，“中序”，“后序”，“按层”，其实这些东西只可意会，不可言传，真的很难在口头

        上说清楚，需要反复的体会递归思想。

            先序：先访问根，然后递归访问左子树，最后递归右子树。（DLR模式）

            中序：先递归访问左子树，在访问根，最后递归右子树。（LDR模式）

            后序：先递归访问左子树，然后递归访问右子树，最后访问根。（LRD模式）

            按层：这个比较简单，从上到下，从左到右的遍历节点。 

  1. #region 二叉树的先序遍历
  2.         /// <summary>
  3. /// 二叉树的先序遍历
  4. /// </summary>
  5. /// <typeparam name="T"></typeparam>
  6. /// <param name="tree"></param>
  7.         public void BinTree_DLR<T>(ChainTree<T> tree)
  8.         {
  9.             if (tree == null)
  10.                 return;
  11.  
  12.             //先输出根元素
  13.             Console.Write(tree.data + "\t");
  14.  
  15.             //然后遍历左子树
  16.             BinTree_DLR(tree.left);
  17.  
  18.             //最后遍历右子树
  19.             BinTree_DLR(tree.right);
  20.         }
  21.         #endregion
  22.  
  23.         #region 二叉树的中序遍历
  24.         /// <summary>
  25. /// 二叉树的中序遍历
  26. /// </summary>
  27. /// <typeparam name="T"></typeparam>
  28. /// <param name="tree"></param>
  29.         public void BinTree_LDR<T>(ChainTree<T> tree)
  30.         {
  31.             if (tree == null)
  32.                 return;
  33.  
  34.             //优先遍历左子树
  35.             BinTree_LDR(tree.left);
  36.  
  37.             //然后输出节点
  38.             Console.Write(tree.data + "\t");
  39.  
  40.             //最后遍历右子树
  41.             BinTree_LDR(tree.right);
  42.         }
  43.         #endregion
  44.  
  45.         #region 二叉树的后序遍历
  46.         /// <summary>
  47. /// 二叉树的后序遍历
  48. /// </summary>
  49. /// <typeparam name="T"></typeparam>
  50. /// <param name="tree"></param>
  51.         public void BinTree_LRD<T>(ChainTree<T> tree)
  52.         {
  53.             if (tree == null)
  54.                 return;
  55.  
  56.             //优先遍历左子树
  57.             BinTree_LRD(tree.left);
  58.  
  59.             //然后遍历右子树
  60.             BinTree_LRD(tree.right);
  61.  
  62.             //最后输出节点元素
  63.             Console.Write(tree.data + "\t");
  64.         }
  65.         #endregion
  66.  
  67.         #region 二叉树的按层遍历
  68.         /// <summary>
  69. /// 二叉树的按层遍历
  70. /// </summary>
  71. /// <typeparam name="T"></typeparam>
  72. /// <param name="tree"></param>
  73.         public void BinTree_Level<T>(ChainTree<T> tree)
  74.         {
  75.             if (tree == null)
  76.                 return;
  77.  
  78.             //申请保存空间
  79.             ChainTree<T>[] treeList = new ChainTree<T>[Length];
  80.  
  81.             int head = 0;
  82.             int tail = 0;
  83.  
  84.             //存放数组
  85.             treeList[tail] = tree;
  86.  
  87.             //循环链中计算tail位置
  88.             tail = (tail + 1) % Length;
  89.  
  90.             while (head != tail)
  91.             {
  92.                 var tempNode = treeList[head];
  93.  
  94.                 head = (head + 1) % Length;
  95.  
  96.                 //输出节点
  97.                 Console.Write(tempNode.data + "\t");
  98.  
  99.                 //如果左子树不为空,则将左子树存于数组的tail位置
  100.                 if (tempNode.left != null)
  101.                 {
  102.                     treeList[tail] = tempNode.left;
  103.  
  104.                     tail = (tail + 1) % Length;
  105.                 }
  106.  
  107.                 //如果右子树不为空，则将右子树存于数组的tail位置
  108.                 if (tempNode.right != null)
  109.                 {
  110.                     treeList[tail] = tempNode.right;
  111.  
  112.                     tail = (tail + 1) % Length;
  113.                 }
  114.             }
  115.         }
  116.         #endregion

<6> 清空二叉树

           虽然C#里面有GC，但是我们能自己释放的就不麻烦GC了，同样清空二叉树节点，我们用到了递归，说实话，这次练习让我喜欢

       上的递归，虽然XXX的情况下，递归的不是很好，但是递归还是很强大的。 

  1. #region 清空二叉树
  2.         /// <summary>
  3. /// 清空二叉树
  4. /// </summary>
  5. /// <typeparam name="T"></typeparam>
  6. /// <param name="tree"></param>
  7.         public void BinTreeClear<T>(ChainTree<T> tree)
  8.         {
  9.             //递的结束点，归的起始点
  10.             if (tree == null)
  11.                 return;
  12.  
  13.             BinTreeClear(tree.left);
  14.             BinTreeClear(tree.right);
  15.  
  16.             //在归的过程中，释放当前节点的数据空间
  17.             tree = null;
  18.         }
  19.         #endregion

最后上一下总的代码 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace ChainTree
  7. {
  8.     public class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             ChainTreeManager manager = new ChainTreeManager();
  13.  
  14.             //插入节点操作
  15.             ChainTree<string> tree = CreateRoot();
  16.  
  17.             //插入节点数据
  18.             AddNode(tree);
  19.  
  20.             //先序遍历
  21.             Console.WriteLine("\n先序结果为： \n");
  22.             manager.BinTree_DLR(tree);
  23.  
  24.             //中序遍历
  25.             Console.WriteLine("\n中序结果为： \n");
  26.             manager.BinTree_LDR(tree);
  27.  
  28.             //后序遍历
  29.             Console.WriteLine("\n后序结果为： \n");
  30.             manager.BinTree_LRD(tree);
  31.  
  32.             //层次遍历
  33.             Console.WriteLine("\n层次结果为： \n");
  34.             manager.Length = 100;
  35.             manager.BinTree_Level(tree);
  36.  
  37.             Console.WriteLine("\n树的深度为：" + manager.BinTreeLen(tree) + "\n");
  38.  
  39.             Console.ReadLine();
  40.  
  41.         }
  42.  
  43.         #region 生成根节点
  44.         /// <summary>
  45. /// 生成根节点
  46. /// </summary>
  47. /// <returns></returns>
  48.         static ChainTree<string> CreateRoot()
  49.         {
  50.             ChainTree<string> tree = new ChainTree<string>();
  51.  
  52.             Console.WriteLine("请输入根节点，方便我们生成树\n");
  53.  
  54.             tree.data = Console.ReadLine();
  55.  
  56.             Console.WriteLine("根节点生成已经生成\n");
  57.  
  58.             return tree;
  59.         }
  60.         #endregion
  61.  
  62.         #region 插入节点操作
  63.         /// <summary>
  64. /// 插入节点操作
  65. /// </summary>
  66. /// <param name="tree"></param>
  67.         static ChainTree<string> AddNode(ChainTree<string> tree)
  68.         {
  69.             ChainTreeManager mananger = new ChainTreeManager();
  70.  
  71.             while (true)
  72.             {
  73.                 ChainTree<string> node = new ChainTree<string>();
  74.  
  75.                 Console.WriteLine("请输入要插入节点的数据：\n");
  76.  
  77.                 node.data = Console.ReadLine();
  78.  
  79.                 Console.WriteLine("请输入要查找的父节点数据：\n");
  80.  
  81.                 var parentData = Console.ReadLine();
  82.  
  83.                 if (tree == null)
  84.                 {
  85.                     Console.WriteLine("未找到您输入的父节点，请重新输入。");
  86.                     continue;
  87.                 }
  88.  
  89.                 Console.WriteLine("请确定要插入到父节点的：1 左侧，2 右侧");
  90.  
  91.                 Direction direction = (Direction)Enum.Parse(typeof(Direction), Console.ReadLine());
  92.  
  93.                 tree = mananger.BinTreeAddNode(tree, node, parentData, direction);
  94.  
  95.                 Console.WriteLine("插入成功，是否继续？  1 继续， 2 退出");
  96.  
  97.                 if (int.Parse(Console.ReadLine()) == 1)
  98.                     continue;
  99.                 else
  100.                     break;
  101.             }
  102.  
  103.             return tree;
  104.         }
  105.         #endregion
  106.     }
  107.  
  108.     #region 插入左节点或者右节点
  109.     /// <summary>
  110. /// 插入左节点或者右节点
  111. /// </summary>
  112.     public enum Direction { Left = 1, Right = 2 }
  113.     #endregion
  114.  
  115.     #region 二叉链表存储结构
  116.     /// <summary>
  117. /// 二叉链表存储结构
  118. /// </summary>
  119. /// <typeparam name="T"></typeparam>
  120.     public class ChainTree<T>
  121.     {
  122.         public T data;
  123.  
  124.         public ChainTree<T> left;
  125.  
  126.         public ChainTree<T> right;
  127.     }
  128.     #endregion
  129.  
  130.     /// <summary>
  131. /// 二叉树的操作帮助类
  132. /// </summary>
  133.     public class ChainTreeManager
  134.     {
  135.         #region 按层遍历的Length空间存储
  136.         /// <summary>
  137. /// 按层遍历的Length空间存储
  138. /// </summary>
  139.         public int Length { get; set; }
  140.         #endregion
  141.  
  142.         #region 将指定节点插入到二叉树中
  143.         /// <summary>
  144. /// 将指定节点插入到二叉树中
  145. /// </summary>
  146. /// <typeparam name="T"></typeparam>
  147. /// <param name="tree"></param>
  148. /// <param name="node"></param>
  149. /// <param name="direction">插入做左是右</param>
  150. /// <returns></returns>
  151.         public ChainTree<T> BinTreeAddNode<T>(ChainTree<T> tree, ChainTree<T> node, T data, Direction direction)
  152.         {
  153.             if (tree == null)
  154.                 return null;
  155.  
  156.             if (tree.data.Equals(data))
  157.             {
  158.                 switch (direction)
  159.                 {
  160.                     case Direction.Left:
  161.                         if (tree.left != null)
  162.                             throw new Exception("树的左节点不为空，不能插入");
  163.                         else
  164.                             tree.left = node;
  165.  
  166.                         break;
  167.                     case Direction.Right:
  168.                         if (tree.right != null)
  169.                             throw new Exception("树的右节点不为空，不能插入");
  170.                         else
  171.                             tree.right = node;
  172.  
  173.                         break;
  174.                 }
  175.             }
  176.  
  177.             BinTreeAddNode(tree.left, node, data, direction);
  178.             BinTreeAddNode(tree.right, node, data, direction);
  179.  
  180.             return tree;
  181.         }
  182.         #endregion
  183.  
  184.         #region 获取二叉树指定孩子的状态
  185.         /// <summary>
  186. /// 获取二叉树指定孩子的状态
  187. /// </summary>
  188. /// <typeparam name="T"></typeparam>
  189. /// <param name="tree"></param>
  190. /// <param name="direction"></param>
  191. /// <returns></returns>
  192.         public ChainTree<T> BinTreeChild<T>(ChainTree<T> tree, Direction direction)
  193.         {
  194.             ChainTree<T> childNode = null;
  195.  
  196.             if (tree == null)
  197.                 throw new Exception("二叉树为空");
  198.  
  199.             switch (direction)
  200.             {
  201.                 case Direction.Left:
  202.                     childNode = tree.left;
  203.                     break;
  204.                 case Direction.Right:
  205.                     childNode = tree.right;
  206.                     break;
  207.             }
  208.  
  209.             return childNode;
  210.         }
  211.  
  212.         #endregion
  213.  
  214.         #region 获取二叉树的深度
  215.         /// <summary>
  216. /// 获取二叉树的深度
  217. /// </summary>
  218. /// <typeparam name="T"></typeparam>
  219. /// <param name="tree"></param>
  220. /// <returns></returns>
  221.         public int BinTreeLen<T>(ChainTree<T> tree)
  222.         {
  223.             int leftLength;
  224.             int rightLength;
  225.  
  226.             if (tree == null)
  227.                 return 0;
  228.  
  229.             //递归左子树的深度
  230.             leftLength = BinTreeLen(tree.left);
  231.  
  232.             //递归右子书的深度
  233.             rightLength = BinTreeLen(tree.right);
  234.  
  235.             if (leftLength > rightLength)
  236.                 return leftLength + 1;
  237.             else
  238.                 return rightLength + 1;
  239.         }
  240.         #endregion
  241.  
  242.         #region 判断二叉树是否为空
  243.         /// <summary>
  244. /// 判断二叉树是否为空
  245. /// </summary>
  246. /// <typeparam name="T"></typeparam>
  247. /// <param name="tree"></param>
  248. /// <returns></returns>
  249.         public bool BinTreeisEmpty<T>(ChainTree<T> tree)
  250.         {
  251.             return tree == null ? true : false;
  252.         }
  253.         #endregion
  254.  
  255.         #region 在二叉树中查找指定的key
  256.         /// <summary>
  257. ///在二叉树中查找指定的key
  258. /// </summary>
  259. /// <typeparam name="T"></typeparam>
  260. /// <param name="tree"></param>
  261. /// <param name="data"></param>
  262. /// <returns></returns>
  263.         public ChainTree<T> BinTreeFind<T>(ChainTree<T> tree, T data)
  264.         {
  265.             if (tree == null)
  266.                 return null;
  267.  
  268.             if (tree.data.Equals(data))
  269.                 return tree;
  270.  
  271.             return BinTreeFind(tree, data);
  272.         }
  273.         #endregion
  274.  
  275.         #region 清空二叉树
  276.         /// <summary>
  277. /// 清空二叉树
  278. /// </summary>
  279. /// <typeparam name="T"></typeparam>
  280. /// <param name="tree"></param>
  281.         public void BinTreeClear<T>(ChainTree<T> tree)
  282.         {
  283.             //递的结束点，归的起始点
  284.             if (tree == null)
  285.                 return;
  286.  
  287.             BinTreeClear(tree.left);
  288.             BinTreeClear(tree.right);
  289.  
  290.             //在归的过程中，释放当前节点的数据空间
  291.             tree = null;
  292.         }
  293.         #endregion
  294.  
  295.         #region 二叉树的先序遍历
  296.         /// <summary>
  297. /// 二叉树的先序遍历
  298. /// </summary>
  299. /// <typeparam name="T"></typeparam>
  300. /// <param name="tree"></param>
  301.         public void BinTree_DLR<T>(ChainTree<T> tree)
  302.         {
  303.             if (tree == null)
  304.                 return;
  305.  
  306.             //先输出根元素
  307.             Console.Write(tree.data + "\t");
  308.  
  309.             //然后遍历左子树
  310.             BinTree_DLR(tree.left);
  311.  
  312.             //最后遍历右子树
  313.             BinTree_DLR(tree.right);
  314.         }
  315.         #endregion
  316.  
  317.         #region 二叉树的中序遍历
  318.         /// <summary>
  319. /// 二叉树的中序遍历
  320. /// </summary>
  321. /// <typeparam name="T"></typeparam>
  322. /// <param name="tree"></param>
  323.         public void BinTree_LDR<T>(ChainTree<T> tree)
  324.         {
  325.             if (tree == null)
  326.                 return;
  327.  
  328.             //优先遍历左子树
  329.             BinTree_LDR(tree.left);
  330.  
  331.             //然后输出节点
  332.             Console.Write(tree.data + "\t");
  333.  
  334.             //最后遍历右子树
  335.             BinTree_LDR(tree.right);
  336.         }
  337.         #endregion
  338.  
  339.         #region 二叉树的后序遍历
  340.         /// <summary>
  341. /// 二叉树的后序遍历
  342. /// </summary>
  343. /// <typeparam name="T"></typeparam>
  344. /// <param name="tree"></param>
  345.         public void BinTree_LRD<T>(ChainTree<T> tree)
  346.         {
  347.             if (tree == null)
  348.                 return;
  349.  
  350.             //优先遍历左子树
  351.             BinTree_LRD(tree.left);
  352.  
  353.             //然后遍历右子树
  354.             BinTree_LRD(tree.right);
  355.  
  356.             //最后输出节点元素
  357.             Console.Write(tree.data + "\t");
  358.         }
  359.         #endregion
  360.  
  361.         #region 二叉树的按层遍历
  362.         /// <summary>
  363. /// 二叉树的按层遍历
  364. /// </summary>
  365. /// <typeparam name="T"></typeparam>
  366. /// <param name="tree"></param>
  367.         public void BinTree_Level<T>(ChainTree<T> tree)
  368.         {
  369.             if (tree == null)
  370.                 return;
  371.  
  372.             //申请保存空间
  373.             ChainTree<T>[] treeList = new ChainTree<T>[Length];
  374.  
  375.             int head = 0;
  376.             int tail = 0;
  377.  
  378.             //存放数组
  379.             treeList[tail] = tree;
  380.  
  381.             //循环链中计算tail位置
  382.             tail = (tail + 1) % Length;
  383.  
  384.             while (head != tail)
  385.             {
  386.                 var tempNode = treeList[head];
  387.  
  388.                 head = (head + 1) % Length;
  389.  
  390.                 //输出节点
  391.                 Console.Write(tempNode.data + "\t");
  392.  
  393.                 //如果左子树不为空,则将左子树存于数组的tail位置
  394.                 if (tempNode.left != null)
  395.                 {
  396.                     treeList[tail] = tempNode.left;
  397.  
  398.                     tail = (tail + 1) % Length;
  399.                 }
  400.  
  401.                 //如果右子树不为空，则将右子树存于数组的tail位置
  402.                 if (tempNode.right != null)
  403.                 {
  404.                     treeList[tail] = tempNode.right;
  405.  
  406.                     tail = (tail + 1) % Length;
  407.                 }
  408.             }
  409.         }
  410.         #endregion
  411.  
  412.     }
  413. }

我们把文章开头的“二叉树”的节点输入到我们的结构中，看看遍历效果咋样。

还没有评论.