树结构

1.1 树的定义

树(Tree)：个节点构成的有限集合
    
    
    
    
    。当n = 0时
    
    
    
    
    ，称为空树     


     


     


     


     


。对于任一棵非空树(n>0)     


     


     


     


     


，它具备以下性质：

树中有一个称为"根(Root)"的特殊节点 




 




 




 




 




，用r表示；其余节点可分为m(m>0)个互不相交的有限集
    
    
    
    
    、

   

   

   

   

   ，...,     

     

     

     

     

，其中每个集合本身又是一棵树  




  




  




  




  




，称为原来树的子树(SubTree) 




 




 




 




 




。如下图：

1.2 树结构的术语

树结构中有很多概念术语


  


  


  


  


  ，在深入讨论树结构之前     
     
     
     
     
，我们先来介绍下跟树结构有关的术语

   

   

   

   

   。为了方便理解记忆   




   




   




   




   




，结合具体的一棵树结构来进行介绍



 



 



 



 



 ，树结构如下：

节点：树中存储的项     

     

     

     

     

。上图中的A-L都是节点  




  




  




  




  




。

根节点：树中最顶端的节点


  


  


  


  


  。在树结构中只有它没有父节点     
     
     
     
     
。上图中的A为根节点   




   




   




   




   




。

节点的度：一个节点含有的子树的个数



 



 



 



 



 。根节点A的度为3；子节点C的度为1                         。

树的度：树中最大节点度    




    




    




    




    




。树中最大节点度为3(根节点A和子节点B的度均为3)                         ，所以树的度为3
























。

子节点(孩子节点)：紧邻一个给定的节点之下    




    




    




    




    




，并且直接与给定节点相连的一个节点                         。一个节点可以有多个子节点     



     



     



     



     



。上图中B-L都是子节点
























。

父节点(双亲节点)：紧邻一个给定节点之上
























，且直接与给定节点相连的一个节点
    
    
    
    
    。一个节点只能有一个父节点     


     


     


     


     


。上图中A     


     


     


     


     


、B 




 




 




 




 




、C

   

   

   

   

   、D     

     

     

     

     

、H都是父节点 




 




 




 




 




。

兄弟节点：拥有共同父节点的子节点

   

   

   

   

   。上图中B  




  




  




  




  




、C


  


  


  


  


  、D是兄弟节点                         ，E     
     
     
     
     
、F   




   




   




   




   




、G也是兄弟节点     

     

     

     

     

。

叶子节点：没有子节点的节点  




  




  




  




  




。或者说度为0的节点


  


  


  


  


  。上图中标绿的几个节点都是叶子节点     
     
     
     
     
。

内部节点：至少有一个子节点的节点   




   




   




   




   




。B



 



 



 



 



 、C                         、D    




    




    




    




    




、H都是内部节点



 



 



 



 



 。

边/分支：将一个父节点连接到其子节点的线                         。上图中的线就是边也称为分支    




    




    




    




    




。

后代(子孙)：以某节点为根的子树中任一节点都称为该节点的后代
























。E
























、F                         、G是节点B的后代；H     



     



     



     



     



、K
























、L是节点C的后代     



     



     



     



     



，B-L的所有节点都是根节点A的后代                         。

祖先：从根到该节点所经分支上的所有节点     



     



     



     



     



。节点D是I
    
    
    
    
    、J的祖先；根节点A是所有节点的祖先
























。

路径：连接一个节点与其后代节点边的序列
    
    
    
    
    。A-B-E和A-C-H-K都可以称作一条路径     


     


     


     


     


。

路径长度：路径中边的数目 




 




 




 




 




。路径A-B-E的路径长度为2；路径A-C-H-K的路径长度为3

   

   

   

   

   。

节点的层次：从根节点定义
























，根节点为第1层
    
    
    
    
    ，根节点的子节点为第2层     


     


     


     


     


，依次类推     

     

     

     

     

。节点的层在上图中已经标出  




  




  




  




  




。

深度(高度)：叶子节点所在的最大层次


  


  


  


  


  。上图中树的深度为4     
     
     
     
     
。

森林：m棵不相交的树的集合   




   




   




   




   




。分别以B     


     


     


     


     


、C 




 




 




 




 




、D为根节点的子树组成的集合可以看做一个森林



 



 



 



 



 。

以上就是树结构的一些术语                         。

1.3 树的分类

树结构可以分为两大类：有序树和无序树    




    




    




    




    




。树中任意节点间没有顺序关系 




 




 




 




 




，那么称其为无序树

   

   

   

   

   ，也称自由树
























。相对的     

     

     

     

     

，树中的任意节点有顺序关系  




  




  




  




  




，称其为有序树                         。在有序树中


  


  


  


  


  ，子节点被视为按照从左到右的顺序排列     
     
     
     
     
，最左边的子节点称为第一个子节点   




   




   




   




   




，最右边的子节点称为最后一个子节点     



     



     



     



     



。我们研究的最多的树结构就是有序树
























。而有序树中最具代表性的树结构就是二叉树
    
    
    
    
    。

二叉树就是度不超过2的有序树结构     


     


     


     


     


。 二叉树中的每个节点最多只能有两个分支



 



 



 



 



 ，分别称为左子树和右子树 




 




 




 




 




。

根据二叉树的定义                         ，会有如下两种极端的二叉树：

​

根据二叉树的形状    




    




    




    




    




，有以下几种常见的二叉树：

平衡二叉树：当且仅当任意节点的两棵子树的高度差不大于1的二叉树

   

   

   

   

   。

完全二叉树：除了最后一层外
























，其他层的节点数目都达到最大的二叉树     

     

     

     

     

。完全二叉树是平衡二叉树的一个特例                         ，完全二叉树最后一层上的节点都是从左到右填充的  




  




  




  




  




。对于一颗k层的完全二叉树     



     



     



     



     



，其节点总数最少的情况是：最后一层只有一个节点
























，此时节点数目为：；其节点总数最多的情况是：最后一层节点数目达到最大
    
    
    
    
    ，即满二叉树     


     


     


     


     


，此时节点数目为：


  


  


  


  


  。对于节点数目为k的完全二叉树 




 




 




 




 




，其深度为：

满二叉树：所有层的节点数目均达到最大的二叉树     
     
     
     
     
。满二叉树是完全二叉树的一个特例   




   




   




   




   




。对于深度为k的满二叉树

   

   

   

   

   ，其节点数目是：；对于节点数目为k的满二叉树     

     

     

     

     

，其深度为：



 



 



 



 



 。

几种二叉树的结构图如下：

关于二叉树还有一个性质：二叉树中叶子节点数为(因为叶子节点的度为0  




  




  




  




  




，所以下标为0)


  


  


  


  


  ，度为2的节点数为      
     
     
     
     
，那么有: n0 = n2 + 1

解析：关于上面等式关系的求解我们可以这样考虑                         。假设二叉树的总节点数为   




   




   




   




   




，因为二叉树的节点度只有0

   

   

   

   

   、1     

     

     

     

     

、2三种情况



 



 



 



 



 ，假设节点度为0  




  




  




  




  




、1


  


  


  


  


  、2的节点数分别为：n0     
     
     
     
     
、n1和n2    




    




    




    




    




。那么有n = n0 + n1 + n2
























。二叉树中节点度为1的节点有1条边连接到其子节点   




   




   




   




   




、节点度为2的节点有2条边连接到其子节点                         ，假设二叉树有E条边    




    




    




    




    




，那么E = n1 + 2n2                         。而我们知道
























，在二叉树中节点总数和边的数目有这样的关系：n = E +1 = n1 + 2n2 + 1     



     



     



     



     



。联立加粗的两个等式                         ，容易得出 n0 = n2 + 1
























。