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

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