数据结构 树与二叉树

数据结构树与二叉树第一页，共二十四页，2022年，8月28日7.7二叉排序树(1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1．定义：二叉排序树(二叉搜索树或二叉查找树)或者是一棵空树；或者是具有如下特性的二叉树(3)它的左、右子树也都分别是二叉排序树。(2)若它的右子树不空，则右子树上所有结点的值均大于等于根结点的值；第二页，共二十四页，2022年，8月28日7.7二叉排序树503080209010854035252388例如:是二叉排序树。66不对二叉排序树进行中序遍历，得到一个有序序列第三页，共二十四页，2022年，8月28日7.7二叉排序树452412145390中序遍历:12,14,24,45,53,90二叉排序树的构造特点：树结构在查找的过程中动态生成。

每次插入的结点只能成为新的叶子结点例：关键字序列为{45，24，53，12，14，90}第四页，共二十四页，2022年，8月28日7.7二叉排序树二叉排序树构造—递归算法与非递归算法p142第五页，共二十四页，2022年，8月28日7.7二叉排序树二叉排序删除节点（1）若被删除节点为叶结点，则可以直接删除（2）若被删除结点没有左子树，则可以用其右子树的跟结点取代被删除结点的位置（3）若被删除结点没有右子树，则可以用其左子树的跟结点取代被删除结点的位置（4）若被删除结点的左、右子树均存在，则要找到右子树中值最小的结点（r），用该节点取代被删除节点的位置。由于由r指出的节点的位置一定没有左子树，所以用其右孩子来取代r所指节点的位置。第六页，共二十四页，2022年，8月28日7.7二叉排序树二叉排序删除节点（1）若被删除节点为叶结点，则可以直接删除（2）若被删除结点没有左子树，则可以用其右子树的跟结点取代被删除结点的位置（3）若被删除结点没有右子树，则可以用其左子树的跟结点取代被删除结点的位置（4）若被删除结点的左、右子树均存在，则要找到右子树中值最小的结点（r），用该节点取代被删除节点的位置。由于由r指出的节点的位置一定没有左子树，所以用其右孩子来取代r所指节点的位置。第七页，共二十四页，2022年，8月28日7.7二叉排序树1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。否则二叉排序树的查找——查找算法若二叉排序树为空，则查找不成功；第八页，共二十四页，2022年，8月28日7.7二叉排序树平均查找长度：确定一个元素在树中的位置所需进行的比较次数节点内路径长度（IPL）：从二叉树根节点到某节点所经过的分枝数，定义为该节点的内经长度二叉树内路径长度：外路径长度（XPL）：外边结点内部结点EPL：二叉树中所有外边结点的路径之和二叉排序树的查找——查找长度第九页，共二十四页，2022年，8月28日7.7二叉排序树查找成功的平均查找长度

ASL=（IPL+n)/n查找失败的平均查找长度

ASL=EPL/n=(IPL+2n)/n平均查找长度

ASL=(IPL+n+EPL)/(n+n+1)=(2IPL+3n)/2n+1二叉排序树的查找——查找长度第十页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用问题的提出：例：编制一个将百分制转换为五级分制的程序。如：

if(a<60)b=”bad”;elseif(a<70)b=”pass”elseif(a<80)b=”general”elseif(a<90)b=”good”elseb=”excellent”;第十一页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用显然，此程序很简单，只要利用条件语句便可完成。如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示：分数0－5960－6970－7980－8990－100比例数0.050.150.400.300.10则80%以上的数据需进行三次或三次以上的比较才能得出结果。第十二页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用叶子结点的权值：对叶子结点赋予的一个有意义的数值量。二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。

记为：WPL=å=nkkklw1第k个叶子的权值；从根结点到第k个叶子的路径长度第十三页，共二十四页，2022年，8月28日编码：给每一个对象标记一个二进制位串来表示一组对象。例：ASCII，指令系统等长编码：表示一组对象的二进制位串的长度相等。不等长编码：表示一组对象的二进制位串的长度不相等。不等长编码什么情况下空间效率高？等长编码什么情况下空间效率高？7.9哈夫曼树及其应用第十四页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀。前缀编码保证了在解码时不会有多种可能。

第十五页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。例：给定4个叶子结点，其权值分别为{2，3，4，7}，可以构造出形状不同的多个二叉树。

WPL=32WPL=41WPL=30234723477423第十六页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.

234723477423第十七页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用第1步：初始化W＝{2，3，4，5}

哈夫曼树的构造过程3524第2步：选取与合并32

5第3步：删除与加入5432

5第十八页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用W＝{2，3，4，5}

哈夫曼树的构造过程重复第2步5432

554

9重复第3步

554

932第十九页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用重复第2步重复第3步

554

932

554

93214W＝{2，3，4，5}

哈夫曼树的构造过程第二十页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用例：一组字符{A,B,C,D,E,F,G}出现的频率分别是{9,11,5,7,8,2,3}，设计最经济的编码方案。第二十一页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用9523510191126871545000000111111ABDCEFG编码方案：A：00B：10C：010D：110E：111F：0110G：0111第二十二页，共二十四页，2022年，8月28日7.9哈夫曼树及其应用哈夫曼算法的存储结构设置一个数组（向量）huffTree[2n-1]保存哈夫曼树中各点的信息，数组（向量）元素的结点结构。weight：权值域，保存该结点的权值；lchild：指针域，结点的左孩子结点在数组中的下标；rchild：指针域，结点的右孩子结点在数组中的下标；parent：指针域，该结点的双亲结点在数组中的下标。

weightlchildrchildparent第二十三页，共二十四页，2022年，8月28日树结构树二叉树逻辑结构逻辑结构存储结构存储结构树的定义基本