《数据结构A》第05章——05.ppt

《《数据结构A》第05章——05.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructuresinC++南京邮电大学计算机学院2006年9月5.5树和森林5.1树的基本概念5.2二叉树5.3二叉树的遍历5.4二叉树遍历的非递归算法5.5树和森林5.6堆和优先权队列5.7哈夫曼树和哈夫曼编码5.8并查集和等价关系南京邮电大学计算机学院2006年9月5.5.1森林与二叉树的转换森林转换成二叉树：将森林中各树的根用线连起来，在树中，凡是兄弟用线连起来；去掉从双亲到除了第一个孩子以外的孩子的连线，只保留双亲到第一个孩子的连线；最后，使之稍微倾斜成习惯的二叉树形。其实，这

2、里讨论的森林是指有序森林，也可将一般的森林视为有序森林来对待。南京邮电大学计算机学院陈慧南2006年9月ABCFFDEGHJABCFFDEGHJABCFFDEGHJ南京邮电大学计算机学院陈慧南2006年9月森林转换成二叉树令F=（T1，T2，…，Tn）是森林，则F所对应的二叉树B(F)为：（1）若F为空，则B为空二叉树。（2）若F非空，则B的根是F中第一棵子树T1的根R1，B的左子树是R1的子树森林（T11，T12，…，T1m）所对应的二叉树，B的右子树是森林（T2，…，Tn）所对应的二叉树。南京邮电大学

3、计算机学院陈慧南2006年9月二叉树转换成森林令B=（R，LB，RB）是二叉树，R是根，LB是左子树，RB是右子树，则B所对应的森林F=（T1，T2，…，Tn）为：（1）若B为空，则F为空森林。（2）若B非空，则F的第一棵树T1的根是二叉树的根R，T1的根的子树森林是B的左子树LB所对应的森林，F中的其余树（T2，…，Tn）是B的右子树RB所对应的森林。南京邮电大学计算机学院陈慧南2006年9月南京邮电大学计算机学院陈慧南2006年9月5.5.2树和森林的存储表示多重链表表示法设度为m的树中有n个结点,总

4、共有n*m个指针域，其中，只有n-1个非空指针域，其余n*m-(n-1)=n(m-1)+1个指针域均为空。elementchild1child2childm南京邮电大学计算机学院陈慧南2006年9月孩子兄弟表示法leftChildelementrightSibling南京邮电大学计算机学院陈慧南2006年9月双亲表示法南京邮电大学计算机学院陈慧南2006年9月三重链表表示法leftChildelementrightSiblingparent南京邮电大学计算机学院陈慧南2006年9月带右链的先序表示法南京

5、邮电大学计算机学院陈慧南2006年9月5.5.3树和森林的遍历按深度方向的遍历由森林和二叉树的转换方法可知，森林中第一棵树的根即二叉树的根，第一棵树的子树组成的森林对应于二叉树的左子树，而除第一棵树外其余树组成的森林是二叉树的右子树，所以，对森林的先序遍历、中序遍历和后序遍历的结果应与对应二叉树的先序、中序和后序遍历的结果完全相同。南京邮电大学计算机学院陈慧南2006年9月先序遍历若森林为空，则遍历结束，否则（a)访问第一棵树的根；（b)按先序遍历第一棵树的根结点的子树组成的森林；（c)按先序遍历除第一棵

6、树外其余树组成的森林。A,B,C,K,D,E,H,F,J,G南京邮电大学计算机学院陈慧南2006年9月中序遍历若森林为空，则遍历结束，否则（a)按中序遍历第一棵树的根结点的子树组成的森林；（b)访问第一棵树的根；（c)按中序遍历除第一棵树外其余树组成的森林。B,K,C,A,H,E,J,F,G,D南京邮电大学计算机学院陈慧南2006年9月后序遍历若森林为空，则遍历结束，否则（a)按后序遍历第一棵树的根结点的子树组成的森林；（b)按后序遍历除第一棵树外其余树组成的森林；（c）访问第一棵树的根。K,C,B,H,

7、J,G,F,E,D,A南京邮电大学计算机学院陈慧南2006年9月按宽度方向的遍历对森林的层次遍历与对应二叉树的层次遍历之间没有逻辑的对应关系南京邮电大学计算机学院陈慧南2006年9月