树和二叉树C

第6章树和二叉树6.1树木的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林二叉树的基本操作6.5二叉树的典型应用6.6哈夫曼树及其应用16.4树和森林6.4.1树木和森林向二叉树的转换6.4.2树木和森林的存储方法6.4.3树木和森林的遍历26.4.1树木和森林向二叉树的转换的回顾1: 如何将树木转换为二叉树？方法: 添加行擦除行旋转左子项-右兄弟表示法兄弟相连的哥哥作为父母，左边的孩子bbcidefghdceif gh3评论2: 如何将二叉树还原为树？重点: 逆向操作，把好孩子变成兄弟！讨论1: 森林如何成为二叉树？即: F = {T1，T2，…，Tm} B = {root，LB，RB}方法1: ①首先将每个森林转换为二叉树； ②依次连接到前一个二叉树的右子树. 方法2: 林直接变成兄弟，然后变成二叉树（请参阅教科书P138中的图6.17，这两种方法都有转换图）. 通过方法1和方法2获得的二叉树完全相同且唯一. 5森林到二叉树示例: （用法二，将森林直接更改为一个兄弟，然后更改为二叉树）AEGB CD F HIBJAAEGB CDFHI兄弟已连接哥哥是父母J头树是根孩子离开了AECCFGDH IJ6讨论2: 如何将二叉树还原到目录林？也就是说，B = {root，LB，RB} F = {T1，T2，…，Tm}要点: 将最右边的子树变成森林，其余的右边子树变成兄弟AAEGBEBFCH ICFGDJDH IJAEGB CD F HIJ76.4.2树森林中有三种常见的树木存储方法: ①家长表示②儿童表示法③儿童兄弟表示法问: 如何通过计算机自动实现树木→二叉树的“连接擦除旋转”？答: 使用“左子右兄弟”的符号进行存储.

存储过程是将树转换为二叉树的过程！ Firstchild数据nextsibling指向左侧的孩子，指向右侧的兄弟8例如: abcdef ghabcdefgh9由于班级时间有限，本PPT页1316“遍历树木和森林”请自学6.5二叉树的典型应用106.4.3树木和森林的遍历深度遍历树优先遍历（先是根，然后是根）树没有中阶遍历（因果树分为左右）广度优先遍历（分层）初遍遍历？访问根节点； •依次遍历根节点的每个子树. •后根遍历•后根依次遍历根节点的每个子树； •访问根节点. 例如: 从头开始的第一根序列: 从头到尾的根序列: 从头到尾ad11讨论: 如果树采用“先变换然后遍历”的方法，结果是否相同？结束结论: 前序遍历: abcd eb c中序遍历: bdcea后序遍历: debc ade树的第一根序列: abcde tree后根序列: bdce a1. 树的预根遍历和二叉树的树序遍历相同； 2.树的后根遍历等效于二叉树的中阶遍历； 3.因为子树没有左或右，所以树没有中阶遍历. 12深度优先遍历（预排序，中间顺序）为什么森林遍历宽度优先遍历（级别）具有中间顺序？第一次遍历AE？如果森林是空的，返回；访问森林中第一棵树的根节点； B CDF？第一根遍历第一树根节点的子树林；第一次遍历将删除树后剩余的第一个A林.

G HIJ？中阶遍历？如果森林是空的，返回；中根遍历森林中第一棵树的根节点的子树森林；访问第一棵树的根节点；删除中间根遍历在第一棵树之后剩余的树木森林. 13例如: AEG预购序列: A B C D E F G H I JB CDFHIJ中间序列: B C D A F E H J I G讨论: 如果采用“先转换后遍历”的方法，结果是否相同？ AB CEFG预序列: A B C D E F G H I J中序列: B C D A F E H J I GDH结论: 在两种I模式下，森林的预序和中序遍历结果都是相同的. J146.5二叉树的典型应用平衡树特性: 所有节点左右子树之间的深度差≤1排序树特性: 所有节点均为“左小右大”字典树二叉排序包括字符串树决定树特征: 分支搜索树（例如，如何仅对三只球称重12个球以区分重量）加权树特征: 具有权重（例如长度）的路径是最优树-是加权路径长度最短树也称为霍夫曼树（Huffman tree），用于通信中的压缩编码. 15什么是平衡二叉树（也称为AVL树）？属性: 所有节点左右子树的深度之差的绝对值≤1如果定义了节点的“平衡因子” BF =左子树的深度–右子树的深度: 则平衡二叉树-1，0，1]中所有节点的BF∈[]示例: 确定以下二叉树是否为AVL树？ -121 -1-10001010 0（a）平衡树（b）不平衡树16什么是二叉排序树？ ----或一棵空树;或具有以下属性的非空二叉树: （1）左子树的所有节点均小于根的值； （2）右子树的所有节点都大于根（3）它的左和右子树也是二叉排序树.

示例: 以下两个图形中的哪个不是二进制排序树？ 552641014310 798（a）2 1367（b）8 9考虑一下: 按顺序遍历它会产生什么影响？ 17什么是决策树？示例: 如何通过仅用天平称重3次来区分12个球？分析: 12个球之一必须轻或重，即总共有24个“劣质产品”的可能性. 每个天平有3种称量结果，称重3次后应获得33 = 27种结果. 说明只有3次发现有缺陷的产品的可能性. 想法: 首先，将12个球分成三组，每组有四个，然后任意分成两组. 将有3个结果: “平衡”或“左>右”或“左<右”. 第二二叉排序树 遍历，我们必须使用已经权衡的结论. 也就是说，要充分利用“旧球”的标准作为参考. 18第一次: 平均分为3组①—④等于=小于<第二次: 3老3新①—③⑨—（11）⑤①—③等于=大于> <<第三次: 1老1新⑤—⑧大于>④⑨—（11）⑤①—③④ ⑨—（11）等于=大于>小于<①（12）小于小于<大于>等于=小于大<小于>等于=小于大<小于>（12）（12）重（11）⑩重⑨重（11）轻⑨轻⑩轻⑥⑦等于=大于>小于<①②等于=大于>小于<⑧⑥⑦轻轻③②①重19什么是正确的树？也就是说，叶子有重量.

例如: a 7 b5 c 2 d 4如果它是加权路径长度最短的树，则最佳二叉树（霍夫曼树）206.6霍夫曼树及其应用1.霍夫曼树2.霍夫曼编码霍夫曼树霍夫曼最佳编码方式二叉树不等长编码加权路径长度最短树是通信中最经典的压缩编码21树. 加权路径长度如何计算？经典示例: nWPL = k = 1 wklk75 2 4 a bc d（a）WPL = 362 c 4 d 75 ab（b）WPL = 46霍夫曼树是最小WPL树中所有叶节点的加权路径长度和7 a5 b24 cd（c）WPL = 3522 1. Huffman树（最佳二叉树）abc术语: d ef g路径: 它由从一个节点到另一个节点的分支组成. 路径长度: 路径上的分支数. 例如: a→e的路径长度= 2树的路径长度: 从树的根到每个节点的路径长度的总和. 树的长度= 10加权路径长度: 从节点到根的路径长度与节点上的权重（WPL）的乘积加权路径树的加权路径长度: 即所有L的权重-树中的叶子节点. 路径长度之和Huffman树: 加权路径长度最小的树. 霍夫曼经常被翻译成霍夫曼，霍夫曼，霍夫曼，霍夫曼等.231. 构造霍夫曼树的基本思想是: 权重最大，WPL最小的节点使用一条短路径，权重小的节点使用长路径路径.

树讨论: 霍夫曼树有什么用？最小冗余编码和有效信息传输的示例: d，i，a，n有4个字符，出现频率分别为7、5、2、4. 如何编码，使包含它们的消息可以最快的速度在网络中传输？方法1: 等长编码（例如二进制编码），令d = 00，i = 01，a = 10，n = 11，则: 高频信息WPL1 = 2bit×（7 + 5 + 2 + 4）= 36使用短代码，低使用长代码，传输方法2: 不等长编码（例如霍夫曼编码）的效率肯定很高！令d = 0; i = 10，a = 110，n = 111，则: WPL2 = 1bit×7 + 2bit×5 + 3bit×（2 + 4）= 35很明显: 要实现霍夫曼编码，必须构造霍夫曼树24首先介绍霍夫曼树的具体构造步骤: 步骤1: 合并，删除和替换权重-在权重集{7,5,2,4}中，始终合并具有最小当前值a的两个权重. 首字母c. 合并{5} {6} d. 合并{7} {11} b. 合并{2} {4}圆框代表内部节点（合并的权重）框代表外部节点（叶子，字符）谁在左边，谁在右边？如果未指定，它将是唯一的. 25step2: 按向左“ 0”和向右“ 1”对霍夫曼树的所有分支进行编号，将霍夫曼树的钩子编号为霍夫曼代码01 d01i 01an霍夫曼编码结果: d = 0，i = 10，a = 110，n = 111 WPL = 1bit×7 + 2bit×5 + 3bit（2 + 4）= 35（小于相等长度的代码WPL = 36）特征: 每个代码将不是另一个代码的前缀，在解码时可以是唯一的恢复的霍夫曼代码也称为前缀代码262. 构造霍夫曼树的步骤（即霍夫曼算法）: （1）由给定的n个权重{w1，w2，…，wn组成的n个二叉树的集合. } F = {T1，T2，…，Tn}（即森林），其中每个二叉树Ti只有一个权重为wi的根节点，其左和右子树为空.

（2）在F中，选择两个根节点权重最小的树作为左右子树，以构造新的二叉树，并使新的二叉树根节点的权重等于左树的根节点和右子树点权重的总和. （3）删除F中的这两棵树，然后将新获得的二叉树添加到F中. （4）重复（2）和（3），直到F仅包含一棵树. 这棵树是霍夫曼树. 简而言之，每次将具有最小当前值的两个权重合并. （此树的特征: 不存在度数为1的节点）思考: 如果权重相同，则首先合并哪个权重？如何证明它是WPL最小的最佳二叉树？请参阅“源代码” 27思维: 霍夫曼编码示例1 [严格问题集6.26③]: 假设用于通信的消息仅包含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的二进制编码方案怎么办？ [类似于P148示例2]解决方案: 首先将概率提高100倍，以方便构造霍夫曼树. 根据霍夫曼树的构造规则（合并，删除，替换），扩大权重集w = {7、19、2、6、32、3、21、10}，可以得到霍夫曼树. 28小结: 1.霍夫曼编码的基本思想: 使用短码表示发生概率较高的信息，使用长码表示发生概率较小的信息，以实现最小冗余. 2.霍夫曼算法的思想: 权重大的节点使用短路径，权重小的节点使用长路径. 3.构造霍夫曼树的步骤: -合并权重（叶子在左侧），删除并替换. 4.霍夫曼编码规则: 左“ 0”，右“ 1”-也称为前缀码，最小冗余码，紧凑代码等，它是数据压缩的基础. 29

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-246381-1.html