8 Chapter5 树与森林的遍历及应用ppt课件

1、数据结构,中国地质大学信息工程学院 2012年秋,第五章 树,3,内容提要,5.1 树的基本概念 5.2 二叉树 5.3 二叉树的存储表示 5.4 二叉树的遍历及其应用 5.6 树与森林 5.7 树与森林的遍历及其应用 5.8 堆及其应用 5.9 Huffman树及其应用,4,5.6 树与森林,1. 树的存储表示,树作为一种数据结构，既可以采用顺序存储结构，也可以采用链式存储结构。,无论采用哪种存储结构，都要求它们既可以存储各结点本身的数据信息，又能够准确地反映树中各结点之间的逻辑关系。,5,1.树的存储表示,双亲表示法：父指针表示 孩子表示法：子女链表表示 双亲-孩子表示法：双亲表示法和孩子

2、表示法 孩子-兄弟表示法：左孩子-右兄弟链表,6,（1）双亲表示法,用一组连续的存储空间（一维数组）存储树中的各结点，同时在每个结点中附设一个指示器，指示其双亲结点在数组中的序号。,Parent: 指示双亲结点,7,双亲表示示例,优点：查找父节点的时间复杂度O(1) 缺点：查找孩子节点的时间复杂度O(n),适用情况：经常需要查找父节点的应用！,8,Data,Parent,First Son,Sibling,Parent: 指示双亲结点 FirstSon：指示第一个孩子结点 Sibling：指示第一个兄弟结点,双亲表示法的改进,9,双亲表示法示例,10,（2）孩子表示法,树中的每个结点有零个或多

3、个孩子结点，可以考虑用一个多重链表表示树，链表中的每个结点包括一个数据域和多个指针域。,数据域：存储树中结点的自身信息； 每个指针域指向该结点的一个孩子结点，通过每个指针反映树中各结点之间的关系。,11,孩子表示法示例,无序树情形链表中各结点顺序任意 有序树必须自左向右链接各个子女结点,12,在一棵树中，由于各结点的度数不一样，因此，结点的指针域个数的设置有两种方法：,（1）每个结点指针域的个数等于该结点的度数；,（2）每个结点指针域的个数等于树的度数：,当各结点的度数相差不大时，可以采用这种存储方法。,多重链表的指针域,13,多重链表示例,缺点：每个节点需要等数量的指针域！,空链域2n+1个

4、,14,孩子表示法的特点,优点：查找孩子节点的时间复杂度O(d) 其中，d为树的度 缺点：查找父节点的时间复杂度O(n),适用情况：经常需要查找孩子节点的应用！,15,（3）双亲-孩子表示法,适用情况：查询父节点和孩子节点均很方便,将双亲表示法和孩子表示法进行有机地结合。,（1）将各结点的孩子结点分别组成单链表；,（2）用一维数组顺序存储树中的各结点： 数组元素包括结点本身的信息、它的双亲结点在数组中的序号、以及该结点的孩子结点链表的头结点。,16,树的双亲-孩子表示法,17,（4）孩子-兄弟表示法,又称二叉树表示法或二叉链表表示法。,左孩子-右兄弟链表表示法,链表中的每个结点有一个信息域和两

5、个指针域。,firstChild域：指向第一个孩子结点； nextSibling域：指向下一个兄弟结点。,18,孩子-兄弟表示法示例,若想找某结点的所有子女， 可先找firstChild，再反复用 nextSibling 沿链扫描。,19,孩子-兄弟表示法的特点,优点：查找孩子节点的时间复杂度O(d) 其中，d为树的度, n为树中结点个数 缺点：查找父节点的时间复杂度O(n),适用情况：经常需要查找孩子节点的应用！,20,树节点定义,template struct TreeNode /树的结点类 T data; /结点数据 TreeNode *firstChild, *nextSibling;

6、 /子女及兄弟指针 TreeNode (T value = 0, TreeNode *fc = NULL, TreeNode *ns = NULL) : data (value), firstChild (fc), nextSibling (ns) /构造函数 ;,21,template class Tree /树类 private: TreeNode *root, *current; /根指针及当前指针 int Find (TreeNode *p, T value); /在以p为根的树中搜索value void RemovesubTree (TreeNode *p); /删除以p为根的子树

7、bool FindParent (TreeNode *t, TreeNode *p); /在以t为根的子树中, 寻找p的父节点，并置为当前节点 public:,树类的定义,便于插入和查询,22,Tree () root = current = NULL; /构造函数 bool Root (); /置根结点为当前结点 bool IsEmpty () return root = NULL; bool FirstChild (); /将当前结点的第一个子女置为当前结点 bool NextSibling (); /将当前结点的下一个兄弟置为当前结点 bool Parent (); /将当前结点的双亲置

8、为当前结点 bool Find (T value); /搜索含value的结点, 使之成为当前结点 /树的其他公共操作 ;,树类的定义（续1）,23,树类的部分实现,template bool Tree:Root () /让树的根结点成为树的当前结点 if (root = NULL) current = NULL; return false; else current = root; return true; ,24,template bool Tree:FindParent (TreeNode *t, TreeNode *p) /在根为*t的树中找*p的双亲, 并置为当前结点 TreeNod

9、e *q = t-firstChild; /*q是*t长子 bool succ; while (q != NULL /未找到 ,树类的部分实现（续1）,25,template bool Tree:Parent () /置当前结点的双亲结点为当前结点 TreeNode *p = current; if (current = NULL | current = root) current = NULL; return false; /空树或根无双亲 return FindParent (root, p); /从根开始找*p的双亲结点 ,树类的部分实现（续2）,26,template bool Tre

10、e:FirstChild () /在树中找当前结点的长子, 并置为当前结点 if (current ,树类的部分实现（续3）,27,template bool Tree:NextSibling () /在树中找当前结点的兄弟, 并置为当前结点 if (current ,树类的部分实现（续4）,28,template bool Tree:Find (TreeNode *p, T Value) /在根为p的树中查找值为value的结点，并使之成为当前结点 bool result=false; if(p-data=value) result=true; current=p; /搜索成功 else T

11、reeNode *q=p-firstChild; while(q!=NULL ,树类的部分实现（续5）,29,template bool Tree:Find (T Value) if(IsEmpty() return false; return Find(root, Value); ,树类的部分实现（续6）,30,2.树与二叉树的转换,二叉树和树都可以用二叉链表作为存储结构，以二叉链表作为媒介可导出树与二叉树的一个对应关系给定一棵树，可以找到唯一的一棵二叉树与之对应。 从物理结构上来看，它们的二叉链表示相同的，只是解释不同而已。,31,如何把树转换成二叉链表形式 ?,1)凡是兄弟就用线连接起来

12、 2)对每个非叶子结点，除其最左孩子外，删去该结点与其他孩子结点的连线 3)以根结点为轴心，顺时针旋转450,32,示例,33,34,3.森林与二叉树的转换,将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。 森林与二叉树表示的转换可以借助树的二叉树表示来实现。,35,T1 T2 T3,A,F,H,T1 T2 T3,A,B,C,D,G,I,J,E,K,F,B,C,D,E,G,H,I,K,J,A,B,C,E,D,H,I,K,J,F,G,3 棵树的森林,各棵树的二叉树表示,森林的二叉树表示,36,森林转化成二叉树的规则,若 F 为空，即 n = 0，则对应的二叉树 B 为空树。 若 F

13、 不空，则 二叉树 B 的根是 F 第一棵树 T1 的根； 其左子树为B (T11, T12, , T1m)，其中，T11, T12, , T1m 是 T1 的根的子树； 其右子树为 B (T2, T3, , Tn)，其中，T2, T3, , Tn 是除 T1 外其它树构成的森林。,37,二叉树转换为森林的规则,如果 B 为空，则对应的森林 F 也为空。 如果 B 非空，则 F 中第一棵树 T1 的根为 B 的根； T1 的根的子树森林 T11, T12, , T1m 是由 B 的根的左子树 LB 转换而来； F 中除了 T1 之外其余的树组成的森林 T2, T3, , Tn 是由 B 的根的

14、右子树 RB 转换而成的森林。,38,4.树的遍历及应用,深度优先遍历 先根次序遍历 后根次序遍历 树中不宜定义中根遍历 广度优先遍历,39,（1）深度优先遍历,树的先根次序遍历,当树非空时 访问根结点 依次先根遍历根的各棵子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现,40,树的先根次序遍历的递归算法,template void Tree:PreOrder ( void (*visit) (BinTreeNode *t) ) /以当前指针current为根, 先根次序遍

15、历 if (!IsEmpty () /树非空 visit (current); /访问根结点 TreeNode *p = current; /暂存当前指针 current = current-firstChild; /第一棵子树 while (current != NULL) PreOrder (visit); /递归先根遍历子树 current = current-nextSibling; current = p; /恢复当前指针 ,41,树的后根次序遍历,当树非空时 依次后根遍历根的各棵子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对

16、应二叉树表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现,42,template void Tree :PostOrder (void (*visit) (BinTreeNode *t) /以当前指针current为根, 按后根次序遍历树 if ( ! IsEmpty () ) /树非空 TreeNode *p = current; /保存当前指针 current = current-firstChild; /第一棵子树 while (current != NULL) /逐棵子树 PostOrder (visit); current = current-nextSibl

17、ing; current = p; /恢复当前指针 visit (current); /访问根结点 ,树的后根次序遍历的递归算法,43,（2）广度优先遍历,按广度优先次序遍历树的结果 ABCDEFG 遍历算法用到一个队列。,44,广度优先（层次次序）遍历算法,template void Tree:LevelOrder(void (*visit) (BinTreeNode *t) ) /按广度优先次序分层遍历树, 树的根结点是当前指针current Queue* Q; TreeNode *p; if (current != NULL) /树不空 p = current; /保存当前指针 Q.En

18、Queue (current); /根结点进队列,45,while (!Q.IsEmpty () Q.DeQueue (current); /退出队列 visit (current); /访问之 current = current-firstChild; while (current != NULL) Q.EnQueue (current); current = current-nextSibling; current = p; /恢复算法开始的当前指针 /IF ,46,5.森林的遍历,森林的遍历也分为深度优先遍历和广度优先遍历 深度优先遍历又可分为先根次序遍历和后根次序遍历。 给定森林 F，若 F = ，则遍历结束。