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

LOGO数据结构数据结构数据结构数据结构20121LOGO第五章第五章第五章第五章 树树树树2内容提要内容提要v5.1 树的基本概念v5.2 二叉树v5.3 二叉树的存储表示v5.4 二叉树的遍历及其应用v5.6 树与森林v5.7 树与森林的遍历及其应用v5.8 堆及其应用v5.9 Huffman树及其应用35.6 5.6 树与森林树与森林n 1. 树的存储表示树的存储表示 树作为一种数据结构，既可以采用顺序存储结构，树作为一种数据结构，既可以采用顺序存储结构，树作为一种数据结构，既可以采用顺序存储结构，树作为一种数据结构，既可以采用顺序存储结构，也可以采用链式存储结构也可以采用链式存储结构也可以采用链式存储结构也可以采用链式存储结构 无论采用哪种存储结构，都要求它们既可以存储无论采用哪种存储结构，都要求它们既可以存储无论采用哪种存储结构，都要求它们既可以存储无论采用哪种存储结构，都要求它们既可以存储各结点本身的数据信息，又能够准确地反映树中各结各结点本身的数据信息，又能够准确地反映树中各结各结点本身的数据信息，又能够准确地反映树中各结各结点本身的数据信息，又能够准确地反映树中各结点之间的逻辑关系。

点之间的逻辑关系点之间的逻辑关系点之间的逻辑关系41.1.树的存储表示树的存储表示v双亲表示法：父指针表示v孩子表示法：子女链表表示v双亲-孩子表示法：双亲表示法和孩子表示法v孩子-兄弟表示法：左孩子-右兄弟链表5（（1 1）双亲表示法）双亲表示法 用一组连续的存储空间（一维数组）存储树用一组连续的存储空间（一维数组）存储树用一组连续的存储空间（一维数组）存储树用一组连续的存储空间（一维数组）存储树中的各结点，同时在每个结点中附设一个指示器，中的各结点，同时在每个结点中附设一个指示器，中的各结点，同时在每个结点中附设一个指示器，中的各结点，同时在每个结点中附设一个指示器，指示其双亲结点在数组中的序号指示其双亲结点在数组中的序号指示其双亲结点在数组中的序号指示其双亲结点在数组中的序号DataParentParent: Parent: Parent: Parent: 指示双亲结点指示双亲结点指示双亲结点指示双亲结点6ABCDEFGdataparentA B C D E F G- -1 0 0 0 1 1 30 1 2 3 4 5 6双亲表示示例双亲表示示例v 优点：查找父节点的时间复杂度优点：查找父节点的时间复杂度O(1)O(1)v 缺点：查找孩子节点的时间复杂度缺点：查找孩子节点的时间复杂度O(n)O(n)适用情况：经常需要查找父节点的应用！适用情况：经常需要查找父节点的应用！7DataParentFirst SonSiblingParent: Parent: 指示双亲结点指示双亲结点FirstSonFirstSon：指示第一个孩子结点：指示第一个孩子结点SiblingSibling：指示第一个兄弟结点：指示第一个兄弟结点双亲表示法的改进双亲表示法的改进8双亲表示法示例A AB BE ED DGGF FC CHHI IJ JL LKKN NMM序号序号dataparent0A-11B02C03D04E15F16G27H38I39J310K511L512M813N8Fsonnext1-142637-1-1510-1-1-1-18129-1-1-111-1-1-113-1-19（（2 2）孩子表示法）孩子表示法 树中的每个结点有零个或多个孩子结点，可以考树中的每个结点有零个或多个孩子结点，可以考树中的每个结点有零个或多个孩子结点，可以考树中的每个结点有零个或多个孩子结点，可以考虑用一个虑用一个虑用一个虑用一个多重链表多重链表多重链表多重链表表示树，链表中的每个结点包括一表示树，链表中的每个结点包括一表示树，链表中的每个结点包括一表示树，链表中的每个结点包括一个个个个数据域数据域数据域数据域和多个和多个和多个和多个指针域指针域指针域指针域。

• 数据域数据域数据域数据域：存储树中结点的自身信息；：存储树中结点的自身信息；：存储树中结点的自身信息；：存储树中结点的自身信息；• 每个指针域每个指针域每个指针域每个指针域指向该结点的一个孩子结点，通过每个指向该结点的一个孩子结点，通过每个指向该结点的一个孩子结点，通过每个指向该结点的一个孩子结点，通过每个指针反映树中各结点之间的关系指针反映树中各结点之间的关系指针反映树中各结点之间的关系指针反映树中各结点之间的关系10孩子表示法示例孩子表示法示例v无序树情形链表中各结点顺序任意无序树情形链表中各结点顺序任意v有序树必须自左向右链接各个子女结点有序树必须自左向右链接各个子女结点ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG012345611 在一棵树中，由于各结点的度数不一样，因此，在一棵树中，由于各结点的度数不一样，因此，在一棵树中，由于各结点的度数不一样，因此，在一棵树中，由于各结点的度数不一样，因此，结点的指针域个数的设置有两种方法：结点的指针域个数的设置有两种方法：结点的指针域个数的设置有两种方法：结点的指针域个数的设置有两种方法：（（（（1 1）每个结点指针域的个数等于该结点的度数；）每个结点指针域的个数等于该结点的度数；）每个结点指针域的个数等于该结点的度数；）每个结点指针域的个数等于该结点的度数；（（（（2 2）每个结点指针域的个数等于）每个结点指针域的个数等于）每个结点指针域的个数等于）每个结点指针域的个数等于树的度数树的度数树的度数树的度数：：：： 当各结点的度数相差不大时，可以采用这种存储当各结点的度数相差不大时，可以采用这种存储当各结点的度数相差不大时，可以采用这种存储当各结点的度数相差不大时，可以采用这种存储方法。

方法多重链表的指针域多重链表的指针域12多重链表示例多重链表示例datapoint1point2point3缺点：每个节点需要等数量的指针域！缺点：每个节点需要等数量的指针域！ABCDEFGABCDEFG                        空链域2n+1个13孩子表示法的特点孩子表示法的特点v 优点：查找孩子节点的时间复杂度优点：查找孩子节点的时间复杂度O(d)其中，其中，d为树的度为树的度v 缺点：查找父节点的时间复杂度缺点：查找父节点的时间复杂度O(n)适用情况：经常需要查找孩子节点的应用！适用情况：经常需要查找孩子节点的应用！123∧45∧6∧∧∧∧∧ABCDEFG012345614（（3 3）双亲）双亲- -孩子表示法孩子表示法适用情况：查询父节点和孩子节点均很方便适用情况：查询父节点和孩子节点均很方便将将将将双亲表示法双亲表示法双亲表示法双亲表示法和和和和孩子表示法孩子表示法孩子表示法孩子表示法进行有机地结合进行有机地结合进行有机地结合进行有机地结合1 1）将各结点的）将各结点的）将各结点的）将各结点的孩子结点孩子结点孩子结点孩子结点分别组成分别组成分别组成分别组成单链表单链表单链表单链表；；；；（（（（2 2）用一维数组顺序存储树中的各结点：）用一维数组顺序存储树中的各结点：）用一维数组顺序存储树中的各结点：）用一维数组顺序存储树中的各结点： 数组元素包括结点本身的信息、它的双亲结点数组元素包括结点本身的信息、它的双亲结点数组元素包括结点本身的信息、它的双亲结点数组元素包括结点本身的信息、它的双亲结点在数组中的序号、以及该结点的孩子结点链表的头在数组中的序号、以及该结点的孩子结点链表的头在数组中的序号、以及该结点的孩子结点链表的头在数组中的序号、以及该结点的孩子结点链表的头结点。

结点15序号序号dataparentlink0A-11B02C03D04E1^5F16G2^7H3^8I39J3^10K5^11L5^12M8^13N8^123^45^6^789^1011^1213^树的双亲树的双亲树的双亲树的双亲- -孩子表示法孩子表示法孩子表示法孩子表示法A AB BE ED DGGF FC CHHI IJ JL LKKN NMM16（（4 4）孩子）孩子- -兄弟表示法兄弟表示法又称又称又称又称二叉树表示法二叉树表示法二叉树表示法二叉树表示法或或或或二叉链表表示法二叉链表表示法二叉链表表示法二叉链表表示法左孩子左孩子左孩子左孩子- -右兄弟链表表示法右兄弟链表表示法右兄弟链表表示法右兄弟链表表示法Ø 链表中的每个结点有一个信息域和两个指针域链表中的每个结点有一个信息域和两个指针域链表中的每个结点有一个信息域和两个指针域链表中的每个结点有一个信息域和两个指针域firstChilddatanextSibling• firstChildfirstChild域：指向域：指向域：指向域：指向第一个孩子结点第一个孩子结点第一个孩子结点第一个孩子结点；；；；• nextSiblingnextSibling域：指向域：指向域：指向域：指向下一个兄弟结点下一个兄弟结点下一个兄弟结点下一个兄弟结点。

17 datafirstChildnextSiblingABCDEFGABCDGFE孩子孩子- -兄弟表示法示例兄弟表示法示例若想找某结点的所有子女，若想找某结点的所有子女，若想找某结点的所有子女，若想找某结点的所有子女，可先找可先找可先找可先找firstChildfirstChild，再反复用，再反复用，再反复用，再反复用 nextSibling nextSibling 沿链扫描沿链扫描沿链扫描沿链扫描18孩子孩子- -兄弟表示法的特点兄弟表示法的特点v 优点：查找孩子节点的时间复杂度优点：查找孩子节点的时间复杂度O(d)其中，其中，d为树的度为树的度, n为树中结点个数为树中结点个数v 缺点：查找父节点的时间复杂度缺点：查找父节点的时间复杂度O(n)适用情况：经常需要查找孩子节点的应用！适用情况：经常需要查找孩子节点的应用！ABCDGFE19树节点定义树节点定义template struct TreeNode {//树的结点类 T data;//结点数据 TreeNode *firstChild, *nextSibling; //子女及兄弟指针 TreeNode (T value = 0, TreeNode *fc = NULL, TreeNode *ns = NULL) : data (value), firstChild (fc), nextSibling (ns) { } //构造函数};20template class Tree {//树类private: TreeNode *root, *current; //根指针及当前指针 int Find (TreeNode *p, T value); //在以p为根的树中搜索value void RemovesubTree (TreeNode *p); //删除以p为根的子树 bool FindParent (TreeNode *t, TreeNode *p); //在以t为根的子树中, 寻找p的父节点，并置为当前节点public:树类的定义树类的定义便于插入和便于插入和查询查询21 Tree () { root = current = NULL; }//构造函数 bool Root (); //置根结点为当前结点 bool IsEmpty () { return root == NULL; } bool FirstChild (); //将当前结点的第一个子女置为当前结点 bool NextSibling (); //将当前结点的下一个兄弟置为当前结点 bool Parent (); //将当前结点的双亲置为当前结点 bool Find (T value); //搜索含value的结点, 使之成为当前结点 …… //树的其他公共操作};树类的定义（续树类的定义（续1 1））22树类的部分实现树类的部分实现template bool Tree::Root () { //让树的根结点成为树的当前结点 if (root == NULL) { current = NULL; return false; } else { current = root; return true; }}23template bool Tree::FindParent (TreeNode *t, TreeNode *p) { //在根为*t的树中找*p的双亲, 并置为当前结点 TreeNode *q = t->firstChild; //*q是*t长子 bool succ; while (q != NULL && q != p) { //扫描兄弟链 if ((succ = FindParent (q, p)) == true) return succ;//递归搜索以*q为根的子树 q = q->nextSibling; } if (q != NULL && q == p) { current = t; return true; } else { current = NULL; return false; } //未找到}树类的部分实现（续树类的部分实现（续1 1））24template bool Tree::Parent () { //置当前结点的双亲结点为当前结点 TreeNode *p = current; if (current == NULL || current == root) { current = NULL; return false; } //空树或根无双亲 return FindParent (root, p);//从根开始找*p的双亲结点}树类的部分实现（续树类的部分实现（续2 2））25template bool Tree::FirstChild () { //在树中找当前结点的长子, 并置为当前结点 if (current && current->firstChild ) { current = current->firstChild; return true; } current = NULL; return false;}树类的部分实现（续树类的部分实现（续3 3））26template bool Tree::NextSibling () { //在树中找当前结点的兄弟, 并置为当前结点 if (current && current->nextSibling) { current = current->nextSibling; return true; } current = NULL; return false;}树类的部分实现（续树类的部分实现（续4 4））27template bool Tree::Find (TreeNode *p, T Value) { //在根为p的树中查找值为value的结点，并使之成为当前结点 bool result=false; if(p->data==value) { result=true; current=p; } //搜索成功 else { TreeNode *q=p->firstChild; while(q!=NULL && ! ( result==Find(q, value))) q=q->nextSibling; } return result; }树类的部分实现（续树类的部分实现（续5 5））28template bool Tree::Find (T Value) { if(IsEmpty()) return false; return Find(root, Value);}树类的部分实现（续树类的部分实现（续6 6））292.2.树与二叉树的转换树与二叉树的转换 二叉树和树都可以用二叉链表作为存储结构，以二叉链表二叉树和树都可以用二叉链表作为存储结构，以二叉链表二叉树和树都可以用二叉链表作为存储结构，以二叉链表二叉树和树都可以用二叉链表作为存储结构，以二叉链表作为媒介可导出树与二叉树的一个对应关系作为媒介可导出树与二叉树的一个对应关系作为媒介可导出树与二叉树的一个对应关系作为媒介可导出树与二叉树的一个对应关系————给定一棵树，给定一棵树，给定一棵树，给定一棵树，可以找到唯一的一棵二叉树与之对应。

可以找到唯一的一棵二叉树与之对应可以找到唯一的一棵二叉树与之对应可以找到唯一的一棵二叉树与之对应 从物理结构上来看，它们的二叉链表示相同的，只是解释从物理结构上来看，它们的二叉链表示相同的，只是解释从物理结构上来看，它们的二叉链表示相同的，只是解释从物理结构上来看，它们的二叉链表示相同的，只是解释不同而已不同而已不同而已不同而已ABCDEFGABCEDGF30如何把树转换成二叉链表形式 ?ABCDEFGBCDGFE         A 1)1)凡是兄弟就用线连接起来凡是兄弟就用线连接起来2)2)对每个非叶子结点，除其最左孩子外，删去该结点对每个非叶子结点，除其最左孩子外，删去该结点与其他孩子结点的连线与其他孩子结点的连线3)3)以根结点为轴心，顺时针旋转以根结点为轴心，顺时针旋转45450 0ABCDEFG31A^D^^G^F^^ECB^K^L^^HI^M^J^^N^A AB BE ED DGGF FC CHHI IJ JL LKKN NMM示例32A AB BE ED DC CGGF FKKL LHHI IJ JMMN NA^D^G^^F^E^CBK^L^^H^IM^J^^N^^333.3.森林与二叉树的转换森林与二叉树的转换v将一般树化为二叉树表示就是用树的子女将一般树化为二叉树表示就是用树的子女- -兄弟表兄弟表示来存储树的结构。

示来存储树的结构v森林与二叉树表示的转换可以借助树的二叉树表森林与二叉树表示的转换可以借助树的二叉树表示来实现示来实现34T1 T2 T3AFHT1 T2 T3ABC DGIJEKFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示35森林转化成二叉树的规则森林转化成二叉树的规则Œ若若 F 为空，即为空，即 n = 0，则对应的二叉树，则对应的二叉树 B 为空树若若 F 不空，则不空，则ü二叉树二叉树 B 的根是的根是 F 第一棵树第一棵树 T1 的根；的根；ü其左子树为其左子树为B (T11, T12, …, T1m)，其中，，其中，T11, T12, …, T1m 是是 T1 的根的子树；的根的子树；ü其右子树为其右子树为 B (T2, T3, …, Tn)，其中，，其中，T2, T3, …, Tn 是除是除 T1 外其它树构成的森林外其它树构成的森林36二叉树转换为森林的规则二叉树转换为森林的规则Œ如果如果 B 为空，则对应的森林为空，则对应的森林 F 也为空如果如果 B 非空，则非空，则üF 中第一棵树中第一棵树 T1 的根为的根为 B 的根；的根；üT1 的根的子树森林的根的子树森林 { T11, T12, …, T1m } 是由是由 B 的根的左子树的根的左子树 LB 转换而来；转换而来；üF 中除了中除了 T1 之外其余的树组成的森林之外其余的树组成的森林 { T2, T3, …, Tn } 是由是由 B 的根的右子树的根的右子树 RB 转换而转换而成的森林。

成的森林374.4.树的遍历及应用树的遍历及应用v 深度优先遍历深度优先遍历u先根次序遍历先根次序遍历u后根次序遍历后根次序遍历u树中不宜定义中根遍历树中不宜定义中根遍历v 广度优先遍历广度优先遍历38（（1 1）深度优先遍历）深度优先遍历v树的先根次序遍历树的先根次序遍历l当树非空时当树非空时l 访问根结点访问根结点l 依次先根遍历根的各棵子树依次先根遍历根的各棵子树l树先根遍历树先根遍历 ABEFCDGl对应二叉树前序遍历对应二叉树前序遍历 ABEFCDGl树的先根遍历结果与其对应二叉树示的前序遍历结果相同树的先根遍历结果与其对应二叉树示的前序遍历结果相同l树的先根遍历可以借助对应二叉树的前序遍历算法实现树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF39树的先根次序遍历的递归算法树的先根次序遍历的递归算法template void Tree::PreOrder ( void (*visit) (BinTreeNode *t) ) { //以当前指针current为根, 先根次序遍历 if (!IsEmpty ()) { //树非空 visit (current); //访问根结点 TreeNode *p = current; //暂存当前指针 current = current->firstChild; //第一棵子树 while (current != NULL) { PreOrder (visit);//递归先根遍历子树 current = current->nextSibling; } current = p;//恢复当前指针 }}40ABCEDGF树的后根次序遍历树的后根次序遍历l当树非空时当树非空时l依次后根遍历根的各棵子树依次后根遍历根的各棵子树l访问根结点访问根结点l树后根遍历树后根遍历 EFBCGDAl对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAl树的后根遍历结果与其对应二叉树表示的中序遍历结果相同树的后根遍历结果与其对应二叉树表示的中序遍历结果相同l树的后根遍历可以借助对应二叉树的中序遍历算法实现树的后根遍历可以借助对应二叉树的中序遍历算法实现41template void Tree ::PostOrder (void (*visit) (BinTreeNode *t)) { //以当前指针current为根, 按后根次序遍历树if ( ! IsEmpty () ) { //树非空 TreeNode *p = current; //保存当前指针 current = current->firstChild; //第一棵子树 while (current != NULL) { //逐棵子树 PostOrder (visit); current = current->nextSibling; } current = p; //恢复当前指针 visit (current); //访问根结点 }}树的后根次序遍历的递归算法树的后根次序遍历的递归算法42（（2 2）广度优先遍历）广度优先遍历v按广度优先次序遍历树的结果按广度优先次序遍历树的结果 ABCDEFGv遍历算法用到一个队列。

遍历算法用到一个队列ABCEDGF43广度优先（层次次序）遍历算法广度优先（层次次序）遍历算法template void Tree::LevelOrder(void (*visit) (BinTreeNode *t) ) { //按广度优先次序分层遍历树, 树的根结点是当前指针current Queue*> Q; TreeNode *p; if (current != NULL) { //树不空 p = current; //保存当前指针 Q.EnQueue (current); //根结点进队列 44 while (!Q.IsEmpty ()) { Q.DeQueue (current); //退出队列 visit (current); //访问之 current = current->firstChild; while (current != NULL) { Q.EnQueue (current); current = current->nextSibling;} } current = p; //恢复算法开始的当前指针 } //IF}455.5.森林的遍历森林的遍历v森林的遍历也分为森林的遍历也分为深度优先遍历深度优先遍历和和广度优先遍历广度优先遍历v深度优先遍历又可分为深度优先遍历又可分为先根次序遍历先根次序遍历和和后根次序遍历后根次序遍历。

v给定森林给定森林 F，若，若 F = Ø，则遍历结束否则，则遍历结束否则v若若F = {{T1 = { r1, T11, …, T1k }, T2, ..., Tm}，则可以导出先，则可以导出先根遍历、后根遍历两种方法其中，根遍历、后根遍历两种方法其中，r1是第一棵树的根是第一棵树的根结点，结点，{T11, …, T1k}是第一棵树的子树森林，是第一棵树的子树森林，{T2, ...,Tm}是除去第一棵树之后剩余的树构成的森林是除去第一棵树之后剩余的树构成的森林深度优先遍历深度优先遍历46若森林若森林F = Ø，返回；否则，返回；否则ü访问森林的根（也是第一棵树的根）访问森林的根（也是第一棵树的根）r1；；ü先根遍历森林第一棵树的根的子树森林先根遍历森林第一棵树的根的子树森林{T11, …, T1k}；；ü先根遍历森林中除第一棵树外其他树组成的先根遍历森林中除第一棵树外其他树组成的森林森林{T2, ...,Tm} 森林的先根次序遍历森林的先根次序遍历ABCEDHIKJFGv森林的先根次序遍历的结果序列森林的先根次序遍历的结果序列ABCDE FG HIKJv这相当于对应二叉树的前序遍历结果。

这相当于对应二叉树的前序遍历结果47森林的后根次序遍历森林的后根次序遍历若森林若森林 F = Ø，返回；否则，返回；否则ü后根遍历森林后根遍历森林 F 第一棵树的根结点的子树森林第一棵树的根结点的子树森林{T11, …, T1k}；；ü访问森林的根结点访问森林的根结点 r1；；ü后根遍历森林中除第一棵树外其他树组成的森林后根遍历森林中除第一棵树外其他树组成的森林{T2, ..., Tm}u森林的后根次序遍历的结果序列森林的后根次序遍历的结果序列 BCEDA GF KIJHu这相当于对应二叉树中序遍历的结果这相当于对应二叉树中序遍历的结果ABCEDHIKJFG48森林的广度优先遍历森林的广度优先遍历AFH BCDGIJ EKABCEDHIKJFGv若森林若森林 F 为空，返回；为空，返回；否则：否则：ü依次遍历各棵树的依次遍历各棵树的根结点；根结点；ü依次遍历各棵树根依次遍历各棵树根结点的所有子女；结点的所有子女；ü依次遍历这些子女依次遍历这些子女结点的子女结点结点的子女结点；ü49本结小结本结小结v 树的存储树的存储v 树与二叉树的转换树与二叉树的转换v 森林与二叉树的转换森林与二叉树的转换v 树的遍历及应用树的遍历及应用v 森林的遍历森林的遍历50。