注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

饥民2011

一直在搬砖

 
 
 

日志

 
 
 
 

数据结构 非线性结构 树 介绍及存储方法  

2013-05-04 16:23:54|  分类: Data structure |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

           所谓树, 其实跟链表有类似的地方,  就是都是由节点和指针构成的数据结构.

           在链表中,  每1个节点(尾节点除外)只有1个指针指向下1个节点. 所以链表各个节点可以由一条线链接起来, 就是一种线性结构.

           而在树中, 每1个节点可以有1个或多个指针指向下1个节点,  如下图:



              所以树是一种非线性结构, 对于这种结构, 有很多算法都要依赖递归来实现, 否则就相当复杂, 所以很多教程都把递归作为1个专题放在树这章之前讲解, 就是这个原因.

              其实树也可以利用连续存储来实现, 也就是说节点不需具有指向别的节点的指针, 但是这种树必须是完全二叉树。 下面会详细提到。

1. 树的定义

         树的定义有两种, 一种是专业的定义, 跟递归有关.

         专业定义:

                 1. 只有1个称为根的节点.

                 2. 有若干个互不相交的子树, 这些子树本身也是树.


                 解析下,子树本身也是树, 就如上上图的树A, 根就是是A了, 它具有2个子树, 分别是B1 和 B2, 而B1和B2也是1棵树啊, 所以, 这个定义跟递归有关.


           通俗定义:

                 1. 树是有节点和边组成.(为什么不用指针这个字眼,用边?因为树是可以利用连续存储来实现的,下面会提到)

                 2. 每1个节点只有1个父节点, 但是可以有多个子节点.

                 3. 但是有1个节点例外, 该节点没有父节点, 此节点就是根节点.



2. 树的一些专业术语.

            节点:

                    构成树的元素, 通常节点里会包含指向其他节点的指针.  在C语言中, 节点通常是由结构体来表示的.


             父节点:

                    节点的上1级节点,  通常1个节点有且只有1个父节点, 根节点例外, 根节点没有父节点.


             子节点:

                    节点的下一级节点, 1个节点可以有1个或多个子节点, 也可以没有子节点.


              子孙:

                    1个节点的子节点或者子节点的子节点....,等所有下级节点都可以成为这个节点的子孙,  1棵树的所有节点都是根节点的子孙.   上图C2 是B1的子孙, 但不是B2的子孙.


              兄弟:

                    拥有同1个父节点的若干个节点成为兄弟, 上图B1 就是 B2的兄弟


              堂兄弟:

                     不属于同1个父节点, 但是它们的父节点属与同1个父节点的若干个节点就是堂兄弟. 上图C1 就是 C3的堂兄弟.


              深度:

                     1棵树从根节点到最底层节点的层数称之为深度.   根节点是第1层.


               叶子节点:

                      没有子节点的节点, 因为叶子不同于树干, 不能再分叉了.  当1个棵树只有1个节点, 那么这个节点是根节点. 也是叶子节点.


               非终端节点:

                       实际就是非叶子节点,  就是具有子节点的节点.


                :

                        1个节点的子节点个数成为这个节点的度

                        1个树中拥有最大度的节点的度就是这个树的度.


               

               森林:

                          n个互不相交的树的集合, 成为森林.         


3. 树的分类

                一般的树:

                          任意1个节点的子节点的个数都不受限制的树.


                二叉树: (binary tree)

                           任意1个节点的个数最多有连个, 且子节点的位置不能被更改, 这种树就是二叉树.

 

                            第一句容易理解, 关键是第二句, 子节点的位置不能更改?   其实意思就是二叉树是有序的, 它的节点最多只有2个子节点, 分别是左子节点和右子节点,  它们的顺序不能被更改. 也不能更改节点的父子点(移动子树),我们称为这种树是有序的树

                            一般的树没有这种要求, 可以是有序的树, 也可以是无序的树(子节点位置可更改),    但是2叉树必须是有序的树.

              

                             二叉树还有分类

               

                           满二叉树: (full binary tree)

                                      在不增加层数的情况下,  无法再多添加1个节点的二叉树, 就是满二叉树. 例如上图那个树就是非满2叉树, 因为还可以添加1个C4节点在B2节点下.

                        

                                        添加了C4节点后, 就是1个满二叉树, 如下图:




                                         假如1个满二叉树的层数是k, 那么它的节点个数必定是 (2^k-1).

                                         这里顺便贴个等比数列求和的推导公式:

                                        
(1)Sn=a1+a2+a3+...+an(公比为q)
(2)q*Sn=a1*q+a2*q+a3*q+...+an*q =a2+a3+a4+...+a(n+1)
(3)Sn-q*Sn=a1-a(n+1)
(4)(1-q)Sn=a1-a1*q^n
(5)Sn=(a1-a1*q^n)/(1-q)
(6)Sn=(a1-an*q)/(1-q)
(7)Sn=a1(1-q^n)/(1-q)

                      完全二叉树: (Complete binary tree)

                                 完全二叉树就厉害了,之前提到满二叉树的目的就是为了引出完全二叉树. 满二叉树是完全二叉树的一种。

                                 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

                                 又有1个通俗定义: 当1棵层数为k满二叉树, 从它的最底层的最右边的节点开始,连续向左删除n个节点(2k >= n >= 0), 得到的树就是1棵完全二叉树.

                                 如下图, 左边两个是完全二叉树, 而右边那个不是,因为最下层的节点不是向右连续的啊!



                            这里补充一点:完全二叉树是效率很高的数据结构,堆是一种完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra算法、Prim算法等都要用 堆才能优化,几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。

                            这里为什么要特别提到完全二叉树呢?  因为完全二叉树是一种重要的数据结构, 跟栈,对列一样, 二叉树也可以用链式和数组内核来实现, 但是因为数组必须是连续存储的, 所以数组实现的二叉树必须是完全二叉树。

                            完全二叉树的性质:

                                   1. 如果知道完全二叉树的节点个数, 就必然可以退出完全二叉树的形状(包括层数, 最后一层的节点排布)。  也就是说两个节点树相同的完全二叉树的形状是一样的。

                                   2. 根据第1个性质, 只需要知道1个确定节点个数的完全二叉树的节点编号, 就可以推出这个节点的父节点和字节点! 这个是1个非常重要的优点!

                           

3. 树的存储(内存)

          3.1 二叉树的存储:

                3.1.1. 连续存储

                       上面提过了, 要利用连续存储(数组)来实现的二叉树必须是完全二叉树, 因为它们的节点必须是连续的啊! 如果要利用连续存储来存储普通的二叉树, 就必须把这个二叉树转化为完全二叉树。

                       关键是如何转化? 很简单, 就是添加必要的空节点把1个非完全二叉树补成1个完全二叉树, 如下图:


                      蓝色的树就是1个普通的2叉树,  白色的节点就是必要的不存放实际数据的节点, 添加上去组成1个完全二叉树, 就可以利用连续存储了。

                      至于要转成完全二叉树的原因:

                      假如只按一定的顺序只存储有效的节点,  内存物理上是1个线性结构, 如果把非线性的树存放在线性的内存中,存放后就变成线性结构了,例如上图中的蓝色树在内存里存放: A,B1,C1,C2,D3,D4  的确是能存放, 但是不能将存放的数据还原成原来的树啊! 所以就必须添加一些无效的节点令它转化成1个完全二叉树!


                      缺点:

                        其实也可以看出, 如过利用连续存储来存放普通的二叉树, 首先需要一定量的连续内存空间,而且必然会造成1些空间浪费。 而且普通二叉树的层数越大, 耗费的内存越大!

                      优点:

                        就是上面完全二叉树的第2个性质,  只需要知道1个节点在数组的位置, 就可以推出它的父节点和子节点, 时间复杂度是0啊!

数据结构 非线性结构 树 介绍及存储方法 - 饥民 - 饥民2011

              3.1.2. 链式存储

                     这个跟链表有点类似。

                     我们会把每1个节点分成4个域, 分别是数据域, 父节点指针域, 左子节点指针域, 右字节域指针域。(或者不包含父节点指针域,则只有3个域)

                     如下图:

数据结构 非线性结构 树 介绍及存储方法 - 饥民 - 饥民2011


                     可以见到,这种存储方式浪费的空间很少, 无非就是一些子节点的空指针, 但是这些空指针个数仍是线性增长的, 但是我们认为浪费的空间已经很少啦, 比起连续存储来讲, 因为链式存储不需存储多余的节点啊。

                    

                  

        

      3.2 一般树的存储:

              一般树的特点是节点的度(子节点个数)无限制, 用上面连续存储根本没可能, 如果用链式存储也很困难, 因为无法决定子节点的子节点指针域的个数啊!

            3.2.1 双亲表示法(数组)

                    双亲表示法实际上也是利用连续存储的, 只不过数组内的元素必须分为两个域, 1个是数据域, 另1个是父节点的下标(注意不是指针啊). 根节点的父节点下标是·-1.

                    双亲表示法对于元素(节点)在数组内的顺序无要求。

                    如下图:


                 如上图右边的数组, 基本上可以把1棵树的结构表示出来了, 但是有个问题, 就是无法通过数组得到同1个父子点兄弟之间的顺序, 例如无法知道C1,C2,C3这个3兄弟在树中的顺序, 所以双亲表示法只适合表示无序的树。

                 优点:

                     几乎不浪费内存空间, 查找父节点很容易。

                 缺点:

                     不能表示有序的树, 查找子节点相对困难, 查找任何1个节点的子节点都必须遍历整个数组。 不能表示有序的树。

数据结构 非线性结构 树 介绍及存储方法 - 饥民 - 饥民2011

          

           3.2.2 孩子表示法(数组)

                 孩子表示法也是利用连续存储来实现的, 它的节点同样具有两个域, 1个是数据域, 另1个是1个子节点下标链表的头节点地址。

                 关键就是这个链表了, 链表的节点有两个域, 1个是int类型,用于表示节点下标, 另1个是指针。

                 如下图:



            可以见到, 因为可以利用子节点下标链表的顺序来表示子节点兄弟的顺序, 所以这种表示法是能表示有序树的。

            优点:

                  查找子节点算法很方便, 可以表示有序树

            缺点:

                 查找父节点算法很困难, 必须遍历每1个节点的子节点下标链表, 如上图, 甚至判断哪个是根节点都需要遍历啊(O(n^2))! 


              

          

        3.2.3 双亲孩子表示法(数组)

         由上面的例子可以看出, 其实双亲表示法和孩子表示法的优缺点是互补的, 所以把它们合拼在一起就是双亲孩子表示法了。

         所谓双亲孩子法就是指表示树的数组内的节点有3个域, 数组域, 父节点下标域,及子节点下标链表域。

         如下图:

        

         优点:

              具有双亲表示法和孩子表示法的所有优点, 关键是方便地查找父节点和子节点。

         缺点:

              占用相对更多的内存空间。


       

       3.2.4 二叉树表示法


        这个的原理就是把一般树转化为二叉树, 然后再利用二叉树的存储方法来存储。

        关键是如何把1个一般树转化为二叉树?  一句话:  每个子节点的左子节点指向它原来的第1个子节点, 右子节点指向它原来的下1个兄弟

        所以这个方法又叫孩子兄弟链表表示法

        如下图:


        可以看到, 转换后层数增加了, 而且某个子树的度越大, 转化后所需的层数越多, 毕竟是利用层数来表示兄弟的个数啊。

        而且有个特点, 就是转化后的二叉树, 对于根节点来讲, 是没有右字数的, 因为根节点没有兄弟嘛。

        优点:

             能使用一些二叉树的算法。

        缺点:

             查找真正的父节点和子节点的算法有点复杂,  例如上图转化后的二叉树, 如果求C3的父节点, 则必须反方向先求出C2和C1..



       

         3.3 森林的存储:


            所谓森林上面也提到过了, 就是互不相交(没有公共节点)的n棵树的集合。

            例如下图中的三棵树就可以组成1个森林。

            



           一般来讲,

           首先: 我们会先把森林的所有树转化为二叉树(孩子兄弟链表表示法)

           然后: 把转化后的二叉树合成1个新的二叉树, 怎么合成? 就是把各个二叉树视为兄弟, 然后新增1个根节点作为它们的父子点。

           其实不难理解的啦, 转化后如图:


        然后就按照二叉树的方法存储就ok了。


  评论这张
 
阅读(331)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017