数据结构与算法Java版课件作者罗文劼第4章节树结构.ppt

* 在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。 下图中的每棵二叉树都有4个结点，且权值相同，但其带权路径长度不同，分别为： （a）WPL＝1×2＋3×2＋5×2＋7×2＝32 （b）WPL＝1×3＋3×3＋5×2＋7×1＝29 （c）WPL＝1×2＋3×3＋5×3＋7×1＝33 （d）WPL＝7×3＋5×3＋3×2＋1×1＝43 （e）WPL＝7×1＋5×2＋3×3＋1×3＝29 * 3．哈夫曼（Haffman）树： 哈夫曼树也称最优二叉树。由上面的例子可见，由相同权值的一组叶子结点所构成的二叉树可能有不同的形态和不同的带权路径长度，具有最小带权路径长度的二叉树称为哈夫曼（Haffman）树，也称最优二叉树。 最优二叉树在实际问题中有很重要的应用。 * 下图给出前面提到的叶结点权值集合为W＝{1，3，5，7}的哈夫曼树的构造过程。可以计算出其带权路径长度为29。 * 2、算法实现 * 4.6.3 最优二叉树的应用--哈夫曼编码 * 4.7 树 4.7.1树的基本操作 树的基本操作通常有以下几种： Initiate(t) Root(x) Parent(t,x) Child(t,x,i) RightSibling(t,x) Insert(t,x,i,s) Delete(t,x, i) Tranverse(t) * 4.7.2 树的表示 1．直观表示法 * 2．嵌套集合表示法 * 3．凹入表示法 4．广义表表示法 (A(B(D,E(H,I),F),C(G))) * 4.7.3 树的存储 1．双亲链表存储方法 * 2．指向孩子的链表存储方法 ⑴多重链表法 令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。 * ⑵孩子链表表示法 * 3．双亲孩子链表存储方法 * 4．孩子兄弟链表存储方法 从树的孩子兄弟表示法可以看到，如果设定一定规则，就可用二叉树结构表示树和森林，这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。 * 4.7.4 树和森林与二叉树之间的转换 1. 树转换为二叉树 * 下图给出森林及其转换为二叉树的过程。 2. 森林转换为二叉树 * 下图给出一棵二叉树还原为森林的过程示意。 3. 二叉树转换为树和森林 * 1. 树的遍历 （1）先序遍历 按照树的先根遍历的定义，对上图所示的树进行先根遍历，得到的结果序列为：A B E F C D G 4.7.5 树或森林的遍历 * 2．后序遍历 按照树的后序遍历的定义，对下图所示的树进行后根遍历，得到的结果序列为： E F B C G D A * 2. 森林的遍历 （1）先序遍历 对于下图所示的森林进行前序遍历，得到的结果序列为： A B C D E F G H J I K * （2）后序遍历 对于下图所示的森林进行中序遍历，得到的结果序列为： B A D E F C J H K I G * 4.7.6 树的应用 1、集合的表示 * 2.集合的运算 * 2．中序遍历 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1) 中序遍历根结点的左子树； (2) 访问根结点； (3) 中序遍历根结点的右子树。 * 对于上图所示的二叉树，按中序遍历所得到的结点序列为： D G B A E C F * 3．后序遍历 后序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1) 后序遍历根结点的左子树； (2) 后序遍历根结点的右子树； (3) 访问根结点。 * 对于上图所示的二叉树，按后序遍历所得到的结点序列为： G D B E F C A * 4.3.2 非递归方法实现二叉树的三种遍历 1、包络线 下图中所示的从根结点左外侧开始，由根结点右外侧结束的曲线，称其为该二叉树的包络线，二叉树的遍历是沿着该线路进行的。沿着该路线按△标记的结点读得的序列为先序序列，按*标记读得的序列为中序序列，按⊕标记读得的序列为后序序列。 * 2、栈的使用