008-树、二叉树及表示法

moc

1、树的简介
定义： 由一个或多个（n ≥ 0）结点组成的有限集合，有且仅有一个结点称为根（root）,当n>1时，其余结点分为m个互不相交的有限集合。每个集合本身有是一棵树，被称为这个树的子树。
树的定义具有递归性，即树中有树。
如果n==0，树为空树。

若干术语：
1. 根  —— 即根结点（没有前驱）
2. 叶子  ——  即终端结点（没有后继）
3. 森林  ——  由m棵互不相交的树组成的集合,如上图去掉根结点，剩下的四棵树构成一个森林。
4. 有序树  —— 结点各子树从左至右有序，不能互换。
5. 无序树 —— 结点各子树可以互换位置。
6. 前驱和后继  
        结点的直接后继称为结点的孩子，结点称为孩子的双亲。
        结点的孩子的孩子称为结点的孙子，结点称为子孙的祖先。
        同一个双亲的孩子之间互称兄弟。
7. 度
        结点的度：结点拥有的子树的数目；
        树的度：树中结点的最大的度。
8. 层次、深度（高度）
        结点的层次：从根到该结点的层数，（根结点算作第一层）；
        树的深度（高度）：指所有节点中最大的层数。
树的表示方法：
        ① 图形表示法
        ② 嵌套集合表示法
        ③ 广义表表示法
        ④ 目录表示法
        ⑤ 孩子表示法
树的逻辑结构：
   一对多（1：n）， 有多个直接后继，但只有一个根结点，且子树之间互不相交。
树的运算：
        ① 普通树（即多叉树）若不能转化为二叉树，则运算很难实现。
        ② 二叉树的运算仍然是插入、删除、修改、查找、排序等，但在这些操作必须建立在对数结点的遍历的基础上。
2、二叉树简介
二叉树是度小于等于2的树，是树中结构最简单，规律性最强的的树。
且可以证明，所有的树都能转化为与之唯一对应的二叉树，不失一般性。
逻辑结构： 一对二（1:2）。
基本特征：
        ① 每个结点最多只有两颗子树，不存在度大于2的结点；
        ② 左子树和右子树的次序不能颠倒（有序树）。
基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

3、二叉树的性质
性质1：  在二叉树的第 i 层上至多有2^(i-1)个结点（i>0）.
性质2：  深度为 k 的二叉树至多有(2^k )- 1个结点，(k>0).
性质3：  对于任何一颗二叉树，若度为2的结点数有n2个，那么叶子结点数n0必定为n2+1个，即n0=n2+1.
        证明：二叉树中全部结点数n = n0 + n1 + n2  (叶子结点数 + 1度结点数 + 2度结点数)；
                 二叉树中全部结点数 n = B +1 (总分支数 + 根结点)
                        （除根结点外，每个结点必有一个直接前驱，即一个分支）
                  总分支数： B = n1 + 2n2 （1度结点必有一个直接后继， 2度结点必有2个）
                  联立上面三个式子可得到：n0 = n2 + 1.
性质4：  具有n个结点的完全二叉树的深度必为：【log2 n】+1.
性质5：  对于完全二叉树，从上至下，从左至右编号， 则编号为 i 的结点，其左孩子编号必为 2i , 其右孩子编号必为2i + 1； 其双亲编号必为 i /2  （i = 1除外）。

满二叉树： 一颗深度为 K 且有2^k - 1 个结点的二叉树。
      特点：  每层都充满了结点。

完全二叉树： 深度为k的，有n个结点的二叉树，当且仅当每一个结点都与满二叉树中编号从1到n的结点一一对应。
         特点：  只有最后一层叶子不满，且全部集中在左边。  ① 第k-1层和满二叉树一样      ② 最后一层，叶子结点尽力靠左。

4、二叉树的存储
1.  顺序存储
①  按照二叉树的结点，“自上而下”，“从左到右”编号，然后用一组连续的存储单元存储。
        若是完全二叉树或满二叉树则顺序存储可以将树复原，否则不可以。
        规律： 下标值为i的双亲，其左孩子的下标值比为2i, 其右孩子必为2i + 1.
② 如果不是完全二叉树，需要补上“虚结点”；
        浪费空间，插入删除操作不方便。
2. 非顺序存储
1.  二叉链表示法

typedef struct BiTNode
{
        int data;
        struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

2.  三叉链表示法

typedef struct TriTNode
{
        int data;
        struct TriTNode *lchild, *rchild;
        struct TriTNode* parent;
}TriTNode, *TriTree;

3.  双亲表示法

// 在子结点中保存了  双亲的位置信息
#define MAX_TREE_SIZE 100
typedef struct BPTNode
{
        int data;
        int parentPosition;  // 指向双亲的指针  // 数组下标
        char LRTag;  // 左右孩子标志域
}BPTNode;

typedef struct BPTree
{
        BPTNode nodes[100];  // 因为结点之间是分散的，需要把结点存储到数组中
        int num_node;   // 结点数目
        int root;   // 根结点的位置，  // 注意此域存储的是父结点在数组的下标
}BPTree;