DS6树最新完整版本.pptVIP

树的其他表示

嵌套集合、广义表表示、凹入表示2.若干术语2.若干术语（续）3.树的逻辑结构(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。例1:双亲表示法2)、用孩子表示法来存储3)、用孩子兄弟表示法来存储例如：5.树的运算1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！（遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。6.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义6.2.2.二叉树的性质满二叉树：一棵深度为k且有2k-1个结点的二叉树。6.2.3二叉树的存储结构讨论：不是完全二叉树怎么办？?空间利用率问题：

在最坏情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)，则需要长度为2k-1的一维数组。二、链式存储结构例：6.3遍历二叉树和线索二叉树对遍历的分析：二叉树先序遍历的非递归描述(1)先序遍历递归算法DLR(bitree*root){if(root!=NULL){printf(“%c”,root-data);DLR(root-lchild);DLR(root-rchild);}}二叉树先序遍历的非递归描述(2)例1:统计二叉树中叶子结点的个数。例2:假若二叉树采用二叉链表作为存储结构，设计算法找二叉树中的某个值x的结点指针。中序遍历：BDCEAFHG

后序遍历：DECBHGFA问：用二叉链表法（l_child,r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？分析：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域。除根结点外，二叉树中每一个结点有且仅有一个双亲（直接前驱），所以只会有n－1个结点的链域存放指针，指向非空孩子结点（即直接后继）。线索二叉树（ThreadedBinaryTree）规定：有关线索二叉树的几个术语：例1：带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。例2：画出以下二叉树对应的中序线索二叉树。6.4树和森林6.4.2.树和森林与二叉树的转换树转二叉树举例：树与二叉树转换讨论2：二叉树怎样还原为树？森林转二叉树举例：（法二）讨论4：二叉树如何还原为森林？树(森林)的遍历先根遍历?对应二叉树的先序遍历后根遍历?对应二叉树的中序遍历6.6Huffman树及其应用Huffman树简介：构造霍夫曼树的基本思想：构造Huffman树的步骤：Huffman算法：——最佳判定算法——最佳判定算法操作要点：按左0右1对Huffman树的所有分支编号！例2：假设用于通信的电文仅由8个字母{a,b,c,d,e,f,g,h}构成，它们在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？为清晰起见，重新排序为:

w={2,3,6,7,10,19,21,32}对应的哈夫曼编码（左0右1）：本章小结要点：把最右边的子树变为森林，其余右子树变为兄弟ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}§6.4.3树和森林的遍历树的遍历可有三条搜索路径:先根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(次序)遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO§6.4.3树和森