008-树、二叉树及表示法
本帖最后由 moc 于 2018-9-30 20:39 编辑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;// 因为结点之间是分散的，需要把结点存储到数组中
int num_node; // 结点数目
int root; // 根结点的位置，// 注意此域存储的是父结点在数组的下标
}BPTree;
页:
[1]