东南大学数据结构与算法分析 非线性结构(树).pptVIP

如果B＝{root,RB,LB}是一棵二叉树，则可按下列规则转换成对应的森林： ? 如果B为空，则对应的森林F也为空。 ? 如果B非空，则F中第一棵树T1的根为root；T1的根的子树森林{T11,T12,…,T1m }是由root的左子树LB转换而来，F中除了T1之外，其余的树组成的森林{ T2,T3,…,Tn }是由root的右子树RB转换而成的森林。 通过演示观察转化过程 二叉树转换为森林的规则 树的遍历 树的二叉树表示 深度优先遍历 （T） （BT） 树的先根次序遍历的递归算法 通过演示观察遍历过程 (1) 访问树的根结点； (2) 依次先根次序遍历根的第一棵子树、第二棵子树、……。 树T的先根次序遍历序列：ABEFCGKLDHIJM 二叉树BT的先序遍历序列：ABEFCGKLDHIJM （T） （BT） 树的后根次序遍历的递归算法 通过演示观察遍历过程 (1) 依次后根次序遍历根的第一棵子树、第二棵子树、……； (2) 访问树的根结点。 树T的后根次序遍历序列：EFBKLGCHIMJDA 二叉树BT的中序遍历序列：EFBKLGCHIMJDA （T） （BT） 森林的遍历 若森林F为空, 返回；否则 ? 访问F的第一棵树的根结点； ? 先根次序遍历第一棵树的根结点的子树森林； ? 先根次序遍历其它树组成的森林。 (1)先根次序遍历的规则 先根次序遍历序列：ABCDEFGHIKJ 若森林F为空，返回；否则 ? 后根次序遍历第一棵树的根结点的子树森林； ? 访问F的第一棵树的根结点； ? 后根次序序遍历其它树组成的森林。 (2) 后根次序遍历的规则 后根次序遍历序列： BCEDAGFKIJH 通过演示观察遍历过程 森林F的先根次序遍历: ABCDEFGHIKJ （F） （BT） 二叉树BT的先序遍历：ABCDEFGHIKJ 森林F的后根次序遍历：BCEDAGFKIJH （F） （BT） 二叉树BT的中序遍历：BCEDAGFKIJH 森林（或树）的先根次序遍历结果与对其相应的二叉树进行先序遍历所得到的结果相同； 森林（或树）的后根次序遍历结果与对其相应的二叉树进行中序遍历所得到的结果相同； 具有不同路径长度的二叉树 5.10 霍夫曼树 (Huffman Tree) 路径(Path)：树中一个结点到另一个结点之间的分支构成了两个结点之间的路径。 路径长度 (Path Length)：两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。 n个结点的二叉树的路径长度不小于下述数列前n项的和，即 其路径长度最小者为: 带权路径长度 ( Weighted Path Length, WPL ) 扩充二叉树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。 若T是一棵具有n个叶结点的二叉树，如果将权值w0,w1,…,wn-1分别赋给T的n个叶结点，则称T是权值为w0,w1,…,wn-1的扩充二叉树。扩充二叉树的叶结点称为外结点，其余结点称为内结点。 具有不同带权路径长度的扩充二叉树 (a) (2+4+5+7)×2＝36 (b)2+4×2+5×3+7×3＝46 (c) 7+5×2+2×3+4×3＝35 霍夫曼树的构造 问题：在给定一组结点后，以这组结点为叶结点，如何构造一棵具有最小带权路径长度的二叉树（霍夫曼树）？ 带权路径长度达到最小的扩充二叉树即为霍夫曼树（最优二叉树）。在霍夫曼树中，权值大的结点离根最近。 霍夫曼树 (1) 由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二叉树的森林F ={T0,T1,T2,…,Tn-1}，其中每一棵扩充二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。 (2)重复以下步骤, 直到F中仅剩下一棵树为止： ① 在F中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 ② 在F中删去这两棵二叉树。 ③ 把新的二叉树加入F。 霍夫曼算法 1、二叉有哪些信誉好的足球投注网站树的查找与顺序结构二分查找的比较； 2、二叉有哪些信誉好的足球投注网站树的结点插入与删除与顺序结构元素插入与删除的比较； 3、树结构有哪些信誉好的足球投注网站效率的进一步提高 问题的提出： 在线性表中，找出某一结点的后继结点很方便。但在如果要在二叉树中找某一结点的某种遍历序列的后继结点则比较困难。比如，对于二叉排序树，如果已知某一结点的关键字，如何找到关键字比它大的下一结点？ 5.7 线索二叉树 (Threaded Binary Tree) 二叉树在一般情况下无法直接找到某结点在某种遍历序列中的前驱和后继结点。由于二叉树是离散存储的，要想建立节点之间的关系，只能通过指针来实