数据结构:树和二叉树定义和术语

1、树的对象
具有相同特性的数据元素的集合
2、关系
如果没有对象叫做空树
否则：
在存在唯一的成为根的数据元素root
当元素个数大于1的时候，其他节点可以
分为互不相交的树，成为根root的子树
        a
 b      c    d
e f     g     
       i   j   
    
b c d 叫做a为root节点的子树
e f 叫做以b为root节点的子树
以此类推 
3、相关术语
结点：数据元素+若干指向子树的分支
      如上数据元素a+指向子树b c d的指针叫做结点
结点的度：分支的个数 比如a的度就为3
树的度：所有结点的度的最大值
叶子结点：度为0的结点
分支结点：度大约0的结点，也就是叶子结点以外的
          特殊的就是root根结点
从根到结点的路径：从根到结点所经历的分支和结点构成


孩子结点：子树的根对于树的根叫做孩子结点
双亲结点：树的根对于子树的根叫做双亲结点
兄弟结点：有相同根的子树叫做兄弟结点
祖先节点：从根到结点之间的全部节点叫做祖先节点
子孙节点：一个根下的所有的节点叫做子孙节点


结点的层次：角色根结点的层次为1，第L层的节点的子树
            根结点的层次是L+1层 
树的深度：树中叶子节点所在的最大层次
如上例子：第3层的i的层次为3+1=4层，整个树的深度为4


森林：是多棵互不相交的树的集合，从定义可以看出，如果一棵树去掉root根结点明显他
      就是一个森林，如果一个森林加上一个root结点那么就是一棵树




有向树：
1、有确定的根
2、树根和子树根之间为有向关系


一般讨论无序树，同一个层次之间无序




和线性表的区别：
第一个元素无前驱 根结点无前驱
最后一个数据元素 多个叶子结点
无后继           无后继
其他数据元素     树中其他节点
一个前驱，       一个前驱、多个后继
一个后继


由于树的不确定性和复杂性我们一般讨论二叉树
二叉树
定义：
二叉树或为空树；或者由一个根结点加上
两棵分别称为左子树和右子树的、互不相交的二叉树组成
并且一个根结点有且只有两个子树为左子树和右子树


       A
  B            E
C            F
  D            G
             H   K
左子树     右子树


二叉树2种形态
1、空树
2、只有根结点的树
3、左子树非空右子树空
4、左子树空右子树非空
5、都不为空


对于3和4不同二叉树必须明确是左子树为空还是右子树为空，虽然
只有一个子树但是必须明确是左子树还是右子树


重要特性：
1、在二叉树的第i层上最多有2^(i-1)个结点(i>=1)
2、深度为h的树结点树最多为2^h-1  
3、对于任何一棵二叉树，如果他含有n0个叶子节点，
   n2个度为2的节点，这必然存在关系n0=n2+1
注：二叉树有3种节点：n0代表度为0的节点
    n1代表度为1的节点
                     n2代表度为2的节点
                     n0+n1+n2=n 总的结点
                     b为分支数量
                     n=b+1=1+n1+2n2
                     及：1+n1+2n2=n0+n1+n2
                     及：n0=n2+1
满二叉树：深度为k的树含有2^k-1个结点，其实就是在一棵树中
          不包含度为1的节点的树，只有深度为k的层末尾节点
          才为叶子结点
完全二叉树：如果给满二叉树编号，按照编号一一对应的一棵树
            及知道结点个数就知道树的结构，且如果无左孩子
            结点那么它就是叶子结点
如：
        1
   2        3
 4   5    6   7 
为满二叉树
        1
   2        3
 4   5    6   
为完全二叉树
        1
   2        3
     4    5
不为完全二叉树


关于完全二叉树的特性：
1、具有n个结点的完全二叉树的深度为 [log2 n]+1 
   符号[]为不大于log2 n的最大整数
2、如果i=1，则结点i是二叉树的根，无双亲，如果i>1，
   这其双亲parent(i)结点为[i/2]
3、如果2i>n则结点i无左孩子，否则左孩子是节点2i
4、如果2i+1>n则结点无右孩子，否则其右孩子是节点2i+1