当前位置:软件学习 > 其它软件 >>

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

 

最近项目赶的紧,歇了一个星期没写博客了,趁周末继续写这个系列。

 

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

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

 

一: 树

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

\

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

www.zzzyk.com

 

 

<2> 添加结点

 

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

 

 1 #region 将指定节点插入到二叉

补充:软件开发 , 其他 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,