树和二叉树(三).ppt

树和森林 树的存储结构 三种常用的表结构 双亲表示法 孩子表示法 孩子兄弟表示法 树的存储结构 双亲表示法 利用除根以外每个结点只有一个双亲的性质 用一组连续空间存储树的结点 每个结点中附设其双亲在链表中的位置指示器 树的存储结构 双亲表示法 如： 这种表示法便于寻找某结点的双亲和树根结点，但寻找孩子结点需遍历整个结构 [HOW?] 树的存储结构 孩子表示法 法一：每个结点有多个指针域，构成多重链表 特点：空间浪费大，操作不便 法二：将结点组成顺序表，每个结点又有自己的孩子链表 树的存储结构 孩子兄弟表示法 以二叉链表作为树的存储结构。又称二叉树表示法，或二叉链表表示法 链表中结点的两个链域分别指向其第一个孩子和下一个兄弟 树的存储结构 树的存储结构 练习 分别给出用双亲表示法、孩子表示法和孩子兄弟表示法表示的树的存储结构 树与二叉树的转换 二叉链表即可用于表示二叉树的存储结构，又可用于表示树的存储结构。 因此，以二叉链表为介，对于给定的树(或森林)，可以确定唯一的一棵二叉树与之对应。反之亦然 森林与二叉树的转换 树与二叉树的对应关系 树 二叉树的转换规则 树中某结点的第一个孩子成为对应二叉树中该结点的左孩子 树中某结点的右兄弟结点成为对应二叉树中该结点的右孩子 树对应的二叉树根结点的右子树总为空 特点：树对应的二叉树中没有右子树 ★自然方法 凡兄弟就用线连，然后去掉父母到子女的连线，只剩下父母到第一个孩子的连线，然后倾斜即可 树与二叉树转换 如 树与二叉树的转换 树与二叉树的对应关系 二叉树 树的转换规则 若某结点是父母的左孩子，则把该结点的右孩子，右孩子的右孩子，…，都与该结点的父结点用线相连，最后去掉所有父母到右子女的连线 如 森林与二叉树的转换 如 森林与二叉树的转换 森林与二叉树的对应关系 森林 二叉树的转换规则 第一棵树的树根为对应的二叉树的根 将各树的树根看成是兄弟 每各树先各自转换为二叉树 将各对应的二叉树集成 特点：森林对应的二叉树中有右子树 森林与二叉树的转换 如 森林与二叉树的转换 森林与二叉树的对应关系 二叉树 森林的转换规则 若某结点是父母的左孩子，则把该结点的右孩子，右孩子的右孩子，…，都与该结点的父结点用线相连，最后去掉所有父母到右子女的连线 如 树(森林)的遍历 先(根次)序遍历 操作 访问头一棵树的根 先(根次)序下遍历头一棵树根的子树 先(根次)序下遍历其它树 相当于对应二叉树的先序遍历 如 树(森林)的遍历 后(根次)序遍历 操作 后(根次)序下遍历第一棵树根的子树 访问头一棵树的根 后(根次)序下遍历其它树 相当于对应二叉树的中序遍历 如 树(森林)的遍历 如 * 树的存储结构 树的遍历操作 树(森林)与二叉树的对应关系 #define MAX_TREE_SIZE 100 Typedef struct PTNnode { TElemType data; int parent; //双亲位置域 }PTNode; Typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; //结点数 }Ptree; R B A C D E F H G K R -1 A 0 B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6 0 1 2 3 4 5 6 7 8 9 树及其双亲表示法存储结构 data child1 child2 … childd data degree child1 child2 … childd (结点同构，d为树的度数) (结点不同构， d为结点的度数) 或 A B C D R E F G H K 3 5 0 1 7 8 6 2 9 R B A C D E F H G K 该结构便于查找孩子结点 0 1 2 3 4 5 6 7 8 9 如何找双亲结点 带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data fc 2 3 4 5 9 7 8 6 ^ ^ ^ ^ ^ ^ ^ ^ ^ 0 1 2 2 3 5 5 5 1 parent a b c d e f h g i Typedef struct CSNode{ ElemType data; struct CSNode *fi