• 1. 数据结构中国地质大学信息工程学院 2015年秋
  • 2. 第五章 树
  • 3. 3内容提要5.1 树的基本概念 5.2 二叉树 5.3 二叉树的存储表示 5.4 二叉树的遍历及其应用 5.6 树与森林 5.7 树与森林的遍历及其应用 5.8 堆及其应用 5.9 Huffman树及其应用
  • 4. 45.6 树与森林 1. 树的存储表示 树作为一种数据结构,既可以采用顺序存储结构,也可以采用链式存储结构。 无论采用哪种存储结构,都要求它们既可以存储各结点本身的数据信息,又能够准确地反映树中各结点之间的逻辑关系。
  • 5. 51.树的存储表示双亲表示法:父指针表示 孩子表示法:子女链表表示 双亲-孩子表示法:双亲表示法和孩子表示法 孩子-兄弟表示法:左孩子-右兄弟链表
  • 6. 6(1)双亲表示法 用一组连续的存储空间(一维数组)存储树中的各结点,同时在每个结点中附设一个指示器,指示其双亲结点在数组中的序号。DataParentParent: 指示双亲结点
  • 7. 7ABCDEFGdataparentA B C D E F G-1 0 0 0 1 1 30 1 2 3 4 5 6双亲表示示例 优点:查找父节点的时间复杂度O(1) 缺点:查找孩子节点的时间复杂度O(n)适用情况:经常需要查找父节点的应用!
  • 8. 8DataParentFirst SonSiblingParent: 指示双亲结点 FirstSon:指示第一个孩子结点 Sibling:指示第一个兄弟结点双亲表示法的改进
  • 9. 9双亲表示法示例ABEDGFCHIJLKNM序号dataparent0A-11B02C03D04E15F16G27H38I39J310K511L512M813N8Fsonnext1-142637-1-1510-1-1-1-18129-1-1-111-1-1-113-1-1
  • 10. 10(2)孩子表示法 树中的每个结点有零个或多个孩子结点,可以考虑用一个多重链表表示树,链表中的每个结点包括一个数据域和多个指针域。 数据域:存储树中结点的自身信息; 每个指针域指向该结点的一个孩子结点,通过每个指针反映树中各结点之间的关系。
  • 11. 11 在一棵树中,由于各结点的度数不一样,因此,结点的指针域个数的设置有两种方法:(1)每个结点指针域的个数等于该结点的度数;(2)每个结点指针域的个数等于树的度数: 当各结点的度数相差不大时,可以采用这种存储方法。多重链表的指针域
  • 12. 12多重链表示例datapoint1point2point3缺点:每个节点需要等数量的指针域!ABCDEFGABCDEFG         空链域2n+1个
  • 13. 13孩子表示法示例无序树情形链表中各结点顺序任意 有序树必须自左向右链接各个子女结点ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456
  • 14. 14孩子表示法的特点 优点:查找孩子节点的时间复杂度O(d) 其中,d为树的度 缺点:查找父节点的时间复杂度O(n)适用情况:经常需要查找孩子节点的应用!123∧45∧6∧∧∧∧∧ABCDEFG0123456
  • 15. 15(3)双亲-孩子表示法适用情况:查询父节点和孩子节点均很方便将双亲表示法和孩子表示法进行有机地结合。(1)将各结点的孩子结点分别组成单链表;(2)用一维数组顺序存储树中的各结点: 数组元素包括结点本身的信息、它的双亲结点在数组中的序号、以及该结点的孩子结点链表的头结点。
  • 16. 16序号dataparentlink0A-11B02C03D04E1^5F16G2^7H3^8I39J3^10K5^11L5^12M8^13N8^123^45^6^789^1011^1213^树的双亲-孩子表示法ABEDGFCHIJLKNM
  • 17. 17(4)孩子-兄弟表示法又称二叉树表示法或二叉链表表示法。左孩子-右兄弟链表表示法 链表中的每个结点有一个信息域和两个指针域。firstChilddatanextSibling firstChild域:指向第一个孩子结点; nextSibling域:指向下一个兄弟结点。
  • 18. 18 datafirstChildnextSiblingABCDEFGABCDGFE孩子-兄弟表示法示例若想找某结点的所有子女, 可先找firstChild,再反复用 nextSibling 沿链扫描。
  • 19. 19孩子-兄弟表示法的特点 优点:查找孩子节点的时间复杂度O(d) 其中,d为树的度, n为树中结点个数 缺点:查找父节点的时间复杂度O(n)适用情况:经常需要查找孩子节点的应用!ABCDGFE
  • 20. 20树节点定义template struct TreeNode { //树的结点类 T data; //结点数据 TreeNode *firstChild, *nextSibling; //子女及兄弟指针 TreeNode (T value = 0, TreeNode *fc = NULL, TreeNode *ns = NULL) : data (value), firstChild (fc), nextSibling (ns) { } //构造函数 };
  • 21. 21template 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:树类的定义便于插入和查询
  • 22. 22 Tree () { root = current = NULL; } //构造函数 bool Root (); //置根结点为当前结点 bool IsEmpty () { return root == NULL; } bool FirstChild (); //将当前结点的第一个子女置为当前结点 bool NextSibling (); //将当前结点的下一个兄弟置为当前结点 bool Parent (); //将当前结点的双亲置为当前结点 bool Find (T value); //搜索含value的结点, 使之成为当前结点 …… //树的其他公共操作 };树类的定义(续1)
  • 23. 23树类的部分实现template bool Tree::Root () { //让树的根结点成为树的当前结点 if (root == NULL) { current = NULL; return false; } else { current = root; return true; } }
  • 24. 24template 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)
  • 25. 25template bool Tree::Parent () { //置当前结点的双亲结点为当前结点 TreeNode *p = current; if (current == NULL || current == root) { current = NULL; return false; } //空树或根无双亲 return FindParent (root, p); //从根开始找*p的双亲结点 }树类的部分实现(续2)
  • 26. 26template bool Tree::FirstChild () { //在树中找当前结点的长子, 并置为当前结点 if (current && current->firstChild ) { current = current->firstChild; return true; } current = NULL; return false; }树类的部分实现(续3)
  • 27. 27template bool Tree::NextSibling () { //在树中找当前结点的兄弟, 并置为当前结点 if (current && current->nextSibling) { current = current->nextSibling; return true; } current = NULL; return false; }树类的部分实现(续4)
  • 28. 28template 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)
  • 29. 29template bool Tree::Find (T Value) { if(IsEmpty()) return false; return Find(root, Value); }树类的部分实现(续6)
  • 30. 302.树与二叉树的转换 二叉树和树都可以用二叉链表作为存储结构,以二叉链表作为媒介可导出树与二叉树的一个对应关系——给定一棵树,可以找到唯一的一棵二叉树与之对应。 从物理结构上来看,它们的二叉链表示相同的,只是解释不同而已。ABCDEFGABCEDGF
  • 31. 31如何把树转换成二叉链表形式 ?ABCDEFGBCDGFEA1)凡是兄弟就用线连接起来 2)对每个非叶子结点,除其最左孩子外,删去该结点与其他孩子结点的连线 3)以根结点为轴心,顺时针旋转450ABCDEFG
  • 32. 32A^D^^G^F^^ECB^K^L^^HI^M^J^^N^ABEDGFCHIJLKNM示例
  • 33. 33ABEDCGFKLHIJMNA^D^G^^F^E^CBK^L^^H^IM^J^^N^^
  • 34. 343.森林与二叉树的转换将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。 森林与二叉树表示的转换可以借助树的二叉树表示来实现。
  • 35. 35T1 T2 T3AFHT1 T2 T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示
  • 36. 36森林转化成二叉树的规则若 F 为空,即 n = 0,则对应的二叉树 B 为空树。 若 F 不空,则 二叉树 B 的根是 F 第一棵树 T1 的根; 其左子树为B (T11, T12, …, T1m),其中,T11, T12, …, T1m 是 T1 的根的子树; 其右子树为 B (T2, T3, …, Tn),其中,T2, T3, …, Tn 是除 T1 外其它树构成的森林。
  • 37. 37二叉树转换为森林的规则如果 B 为空,则对应的森林 F 也为空。 如果 B 非空,则 F 中第一棵树 T1 的根为 B 的根; T1 的根的子树森林 { T11, T12, …, T1m } 是由 B 的根的左子树 LB 转换而来; F 中除了 T1 之外其余的树组成的森林 { T2, T3, …, Tn } 是由 B 的根的右子树 RB 转换而成的森林。
  • 38. 384.树的遍历及应用 深度优先遍历 先根次序遍历 后根次序遍历 树中不宜定义中根遍历 广度优先遍历
  • 39. 39(1)深度优先遍历树的先根次序遍历当树非空时 访问根结点 依次先根遍历根的各棵子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF
  • 40. 40树的先根次序遍历的递归算法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; //恢复当前指针 } }
  • 41. 41ABCEDGF树的后根次序遍历当树非空时 依次后根遍历根的各棵子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现
  • 42. 42template 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); //访问根结点 } }树的后根次序遍历的递归算法
  • 43. 43(2)广度优先遍历按广度优先次序遍历树的结果 ABCDEFG 遍历算法用到一个队列。 ABCEDGF
  • 44. 44广度优先(层次次序)遍历算法template void Tree::LevelOrder(void (*visit) (BinTreeNode *t) ) { //按广度优先次序分层遍历树, 树的根结点是当前指针current Queue*> Q; TreeNode *p; if (current != NULL) { //树不空 p = current; //保存当前指针 Q.EnQueue (current); //根结点进队列
  • 45. 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. 465.森林的遍历森林的遍历也分为深度优先遍历和广度优先遍历 深度优先遍历又可分为先根次序遍历和后根次序遍历。 给定森林 F,若 F = Ø,则遍历结束。否则 若F = {{T1 = { r1, T11, …, T1k }, T2, ..., Tm},则可以导出先根遍历、后根遍历两种方法。其中,r1是第一棵树的根结点,{T11, …, T1k}是第一棵树的子树森林,{T2, ...,Tm}是除去第一棵树之后剩余的树构成的森林。深度优先遍历
  • 47. 47若森林F = Ø,返回;否则 访问森林的根(也是第一棵树的根)r1; 先根遍历森林第一棵树的根的子树森林{T11, …, T1k}; 先根遍历森林中除第一棵树外其他树组成的森林{T2, ...,Tm}。 森林的先根次序遍历ABCEDHIKJFG森林的先根次序遍历的结果序列 ABCDE FG HIKJ 这相当于对应二叉树的前序遍历结果。
  • 48. 48森林的后根次序遍历若森林 F = Ø,返回;否则 后根遍历森林 F 第一棵树的根结点的子树森林{T11, …, T1k}; 访问森林的根结点 r1; 后根遍历森林中除第一棵树外其他树组成的森林{T2, ..., Tm}。森林的后根次序遍历的结果序列 BCEDA GF KIJH 这相当于对应二叉树中序遍历的结果。ABCEDHIKJFG
  • 49. 49森林的广度优先遍历AFH BCDGIJ EKABCEDHIKJFG若森林 F 为空,返回; 否则: 依次遍历各棵树的 根结点; 依次遍历各棵树根 结点的所有子女; 依次遍历这些子女 结点的子女结点; 
  • 50. 50本结小结 树的存储 树与二叉树的转换 森林与二叉树的转换 树的遍历及应用 森林的遍历
  • 51. 作业P248 5.17 (树转化为二叉树)51