先序遍历算法.ppt

5.3.3 线索二叉树 (b) 中序线索二叉树 5.3.3 线索二叉树 (c) 后序线索二叉树 中序线索二叉树的完整的线索树存储 中序线索二叉树的存储示意 中序线索树的完整的线索树存储 中序线索树的存储示意 5.4 树 和 森 林 5.4.1 树、森林与二叉树的转换 （1）一般树转换为二叉树 （2）二叉树还原为一般树 （3）森林转换为二叉树 （4）二叉树还原为森林 一般树转换为二叉树 （1）加线。在所有兄弟结点之间加一连线。 （2）抹线。对每个结点，仅保留它与其最左一个孩子的连线，去掉该结点与其他孩子的连线。 （3）旋转。以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。 一般树转换为二叉树 二叉树还原为一般树 （1）加线。若某结点是其双亲结点的左孩子，则将该结点的右孩子及连续地沿着右孩子的右链不断有哪些信誉好的足球投注网站到的所有右孩子都分别与该结点的双亲结点用线连接。 （2）抹线。把原来二叉树中所有双亲结点与其右孩子的连线抹去。 （3）整理上述两步得到的一般树，使之结构分明。 二叉树还原为一般树 森林转换为二叉树 ①将森林中的每棵子树转换成相应的二叉树，形成有若干二叉树的森林； ②按森林中树的先后次序，依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树，这样整个森林就生成了一棵二叉树。 森林转换为二叉树 二叉树还原为森林 ①抹线。将二叉树的根结点与其右孩子的连线及连续地沿着右链不断地有哪些信誉好的足球投注网站到的所有右孩子的连线抹去，这样就得到包含若干棵二叉树的森林； ②还原。将每棵二叉树按二叉树还原为一般树的方法还原为一般树，即可得到由一般树组成的森林。 5.4.2 树和森林的存储结构 1）双亲表示法 以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。 5.4.2 树和森林的存储结构 2）孩子表示法 将树中每个结点的孩子结点用一个单链表（孩子链表）表示，那么，一棵树有n个结点就有n个孩子链表（度为0的结点，所对应的孩子链表为空表）。将这n个孩子链表的头指针用一个指针数组来存储，这就构成了树的孩子表示法的存储结构。 5.4.2 树和森林的存储结构 3）孩子兄弟表示法 以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。 5.4.3树和森林的遍历 1．按深度优先遍历 （1）先序遍历算法： 若森林为空，则遍历结束； 否则 访问第一棵树的根； 按先序遍历第一棵树的根结点的子树组成的森林； 按先序遍历除第一棵树外其余树组成的森林。 5.4.3树和森林的遍历 1．按深度优先遍历 （2）中序遍历算法： 若森林为空，则遍历结束； 否则 按中序遍历第一棵树的根结点的子树组成的森林； 访问第一棵树的根； 按中序遍历除第一棵树外其余树组成的森林。 5.4.3树和森林的遍历 1．按深度优先遍历 （3）后序遍历算法： 若森林为空，则遍历结束； 否则 按后序遍历第一棵树的根结点的子树组成的森林； 按后序遍历除第一棵树外其余树组成的森林； 访问第一棵树的根。 5.4.3树和森林的遍历 2．按宽度优先遍历 二叉树可以按层次遍历，一般树和森林也可按层次遍历。具体做法是：首先访问处于第一层的全部结点，然后访问处于第二层的结点，再访问第三层，??，最后访问最下层的结点，但森林或树的层次遍历序列与对应的二叉树的层次遍历序列没有必然的逻辑关系。 哈夫曼树：又称最优二叉树，它是n个带叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。 5.5 哈夫曼树极其应用 5.5.1 哈夫曼树的概念及构造 1．基本概念 （1）路径长度：由树中一个结点到另一结点的分支构成这两个结点之间的路径，路径上分支的数目称为路径长度。 （2）树的路径长度：从根结点到每一个结点的路径长度之和。 （3）结点的带权路径长度：从根结点到某个结点的路径长度与该结点所带的权值的乘积。 （4）树的带权路径长度：树中所有叶子结点的带权路径长度之和。 2．哈夫曼树的构造 （1）根据给定的n个权值{w1，w2，…，wn}构成n棵二叉树的集合F{T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。 （2）在F中选取两棵根结点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树的根结点的根权值为其左、右子树上根结点的权值之和。 （3）在F中删除这两棵树，同时将新得到的二叉树加入F中。 （4）重复（2）和（3），直到F只含一棵树为止。这棵