树和二叉树-数据结构.ppt

第6章树和二叉树 树的定义和基本术语二叉树遍历二叉树和线索二叉树树和森林哈夫曼树及其应用 本章学习要点 掌握树和二叉树的性质 相关术语及基本概念 二叉树的两种存储方法 重点是链式存储据 二叉树三种顺序遍历及其递归实现算法 二叉树的层次遍历创建链式存储的二叉树的算法 中序线索二叉树的算法 中序线索二叉树上基本算法 遍历 求指定结点的前驱和后继 查找指定值的结点 树的遍历算法 先根遍历 后根遍历 森林的遍历算法 前序遍历 后序遍历 哈夫曼树的概念 哈夫曼树的构造算法 哈夫曼编码通过本章的算法的学习 让学生认识到递归定义的数据结构之下求解相应问题 思路清晰和简洁算法设计方法是采用递归的方式 理解二叉树三种遍历的非递归算法及其与栈的关系在中序线索树指定结点下插入新结点的算法 学会在复杂情形下分类讨论的方法 树的三种存储结构 双亲表示法 孩子表示法 孩子兄弟表示法 及各自的特点 优点 缺点 掌握树 森林和对应的二叉树相互转换算法 本章作业 6 36 56 76 126 136 196 216 276 296 426 43 本章教学重点和难点 教学重点二叉树的性质 二叉树的链式存储 二叉树三种顺序遍历算法 遍历算法的应用 中序线索二叉树的算法及其简单应用 哈夫曼树的构造和编码算法 注意程序实现方法教学难点二叉树性质的运用二叉树三种遍历的非递归算法 中序线索二叉树的理解及先序后序线索算法的实现 二叉树中 学会递归的思想求解问题 用遍历的典型算法解决一些具体问题 第6章树和二叉树 树型结构是一类重要的非线性数据结构 其中常见的是树和二叉树树是以分支关系定义的层次结构树结构在客观世界中广泛存在人类社会的族谱社会组织结构在计算机领域编译程序中表示源程序的语法结构数据库中是信息的重要组织形式之一操作系统中的进程管理本章主要讨论二叉树的存储及各种操作研究树和森林与二叉树的转换关系树的应用 6 1树的定义和基本术语 树 tree 是n n 0 个结点的有限集 在任意一颗非空树中有且仅有一个特定的称为根 root 的结点 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一颗树 并且称为根的子树 SubTree 特点没有结点的树称为空树树中各子树是互不相交的 树的示例 根 子树 抽象数据类型树的定义 ADTTree 数据对象D D是具有相同特性的数据元素的集合 数据关系R 若D为空集 则称为空树若D仅含一个数据元素 则R为空集 否则R H H是如下二元关系 1 在D中存在唯一的称为根的数据元素root 它在关系H下无前驱 2 若D root 则存在D root 的一个划分 D1 D2 Dm m 0 对任意j k 1 j k m 有Dj Dk 且对任意的i 1 i m 唯一存在数据元素xi Di 有 H 3 对应于D root 的划分 H 有唯一的一个划分H1 H2 Hm m 0 对任意j k 1 j k m 有Dj Dk 且对任意的i 1 i m Hi是D上的二元关系 Di Hi 是一颗符合本定义的树 称为根root的子树基本操作InitTree Assign T cur e value Parent T cur e LeftChild T cur e RightChild T cur e InsertTree T p I c DeleteTree T p i TraverseTree T visit ADTTree 基本术语 结点 node 包括一个数据元素及若干指向其子树的分支结点的度 degree 结点拥有的子树数叶子 leaf 或终端结点 度为0的结点非终端结点或分支结点 度不为0的结点内部结点 除根结点外的分支结点树的度 树中各结点度的最大值孩子 child 结点的子树的根称为该结点的孩子双亲 parents 孩子结点的上层结点叫该结点的双亲兄弟 sibling 同一个双亲的孩子互为兄弟祖先 从根结点到该结点所经分支上的所有结点子孙 以某结点为根的子树中的任一结点称为根的子孙结点的层次 level 从根结点算起 根为第一层 它的孩子为第二层 堂兄弟 双亲在同一层的结点互为堂兄弟深度 depth 或高度 树中结点的最大层次数有序树 树中结点的子树从左到右是有序的第一孩子 有序树中最左的子树的根最后孩子 有序树中最右的子树的根无序树 树中结点的子树没有前后次序森林 forest m m 0 棵互不相交的树的集合 术语示例 结点A的度 3结点B的度 2结点M的度 0 叶子 K L F G M I J 结点A的孩子 B C D结点B的孩子 E F 结点I的双亲 D结点L的双亲 E 结点B C D为兄弟结点K L为兄弟 结点A的层次 1结点M的层次 4 树的深度 4 结点F G为堂兄弟结点A是结点F G的祖先 6 2二叉树 BinaryTree 定义 二叉树是n n 0 个结点的有限集 它或为空树 n 0 或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树 即不存在度大于2的结点 二叉树的子树有左 右之分 且其次序不能任意颠倒基本形态 抽象数据类型二叉树的定义 ADTBinaryTree 数据对象D D是具有相同特性的数据元素的集合 数据关系R 若D为空集 则称为空树若D仅含一个数据元素 则R为空集 否则R H H是如下二元关系 1 在D中存在唯一的称为根的数据元素root 它在关系H下无前驱 2 若D root 则存在D root Dl Dr 且Dl Dr 3 若Dl 则D1中存在唯一的元素xl H 且存在Dl上的关系Hl H 若Dr 则Dr中存在唯一的元素xr H 且存在Dr上的关系Hr H H Hl Hr 4 Dl Hl 是一颗符合本定义的二叉树 称为根的左子树 Dr Hr 是一颗符合本定义的二叉树 称为根的右子树 基本操作InitBiTree Assign T cur e value Parent T cur e LeftChild T cur e RightChild T cur e LeftBibling T e RightSibling T e InsertChild T p LR c DeleteChild T p LR c ProOrderTraverse T Visit 先序遍历二叉树InOrderTraverse T Visit 中序遍历二叉树PostOrderTraverse T Visit 后序遍历二叉树LevelOrderTraverse T Visit 层次遍历二叉树 ADTBinaryTree 二叉树的性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 归纳法证明i 1时 只有一个根结点 显然21 1 20 1 成立 假设对于所有的j 1 j i成立 即第j层最多2j 1个结点 那么可以证明j i时成立 由归纳假设 第i 1层上至多2 i 1 1个结点 由于二叉树的每个结点的度最多为2 故在第i层上的最大结点数为第i 1层上最大结点数的2倍 即2x2 i 1 1 2i 1 证明完毕 二叉树的性质 性质2 深度为k的二叉树至多有2k 1个结点 k 1 证明由性质1可见 深度为k的二叉树的最大结点数为 二叉树的性质 性质3 对任何一颗二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1证明设n1为二叉树T中度为1的结点数因为二叉树中所有结点的度均小于或等于2 则n n0 n1 n2 1 分析分支数的关系 除了根结点外 其余结点都有且只有一个分支进入 设B为分支总数 则n B 1由于这些分支都是由度为1或2的结点发出的 故B n1 2n2于是 n n1 2n2 1 2 由 1 和 2 得n0 n2 1证毕 几种特殊形式的二叉树 满二叉树定义 一颗深度为k且有2k 1个结点的二叉树称为满二叉树 特点 每一层上的结点数都是最大结点数完全二叉树定义 深度为k 有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时 称为完全二叉树特点叶子结点只可能在层次最大的两层上出现对任一结点 若其右分支下子孙的最大层次为i 则其左分支下子孙的最大层次必为i或i 1 完全二叉树示例 二叉树的性质 性质4 具有n个结点的完全二叉树的深度为证明假设深度为k 则根据性质2和完全二叉树的定义有于是k 1 log2n k 因为k是整数 所以 二叉树的性质 性质5 如果对一颗有n个结点的完全二叉树 其深度为 的结点按层次编号 从1层到第层 每层从左到右 则对任一结点i 1 i n 有 如果i 1 则结点是二叉树的根 无双亲 如果i 1 则其双亲PARENT i 是结点 如果2i n 则结点i无左孩子 结点i为叶子结点 否则其左孩子LCHILD i 是结点2i 如果2i 1 n 则结点i无右孩子 结点i为叶子结点 否则其右孩子RCHILD i 是结点2i 1 二叉树的存储结构 顺序存储结构 存储顺序存储结构实现 按满二叉树的结点层次编号 依次存放二叉树中的数据元素特点 结点间关系蕴含在其存储位置中浪费空间 适于存满二叉树和完全二叉树 defineMAX TREE SIZE100 二叉树的最大结点数typedefTElemTypeSqBiTree MAX TREE SIZE 0号单元存储根结点SqBiTreebt 二叉树的存储结构 二叉链表 二叉链表typedefstructBiTNode TElemTypedata structBiTNode lchild rchild BiTNode BiTree 在n个结点的二叉链表中 有n 1个空指针域 二叉树的二叉链表存储表示 二叉树的二叉链表存储表示 typedefstructBiTNode TElemTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree 基本操作的函数原型说明 statusCreateBiTree Bitree T StatusPreOrderTraverse BiTreeT Status visit TElemTypee StatusInOrderTraverse BiTreeT Status visit TElemTypee StatusPostOrderTraverse BiTreeT Status visit TElemTypee StatusLevelOrderTraverse BiTreeT Status visit TElemTypee 二叉树的存储结构 三叉链表 三叉链表typedefstructTNode TElemTypedata structTNode lchild rchild parent TNode TTree 二叉树存储方式的比较 在不同的存储结构中 实现二叉树的操作方法不同具体应用中根据二叉树的形态结合操作采用合适的存储结构InitBiTree T DestroyBiTree T CreateBiTree T definition ClearBiTree T BiTreeEmpty T BiTreeDepth T Root T Value T cur e Assign T cur e value Parent T cur e LeftChild T cur e RightChild T cur e LeftBibling T e RightSibling T e InsertChild T p LR c DeleteChild T p LR c ProOrderTraverse T Visit InOrderTraverse T Visit PostOrderTraverse T Visit LevelOrderTraverse T Visit 例题选择题1 5 1 下面关于二叉树的结论正确的是A 二叉树中 度为O的结点个数等于度为2的结点个数加1 B 二叉树中结点个数必大于O C 完全二叉树中 任何一个结点的度 或者为O 或者为2 D 二叉树的度是2 分析 该题主要考查二叉树逻辑结构的特点 正确答案为A 二叉树中结点个数可以为O 称为空树 所以B错 满二叉树中 任何一个结点的度 或者为O 或者为2 完全二叉树中 任何一个结点的度 或者为O 或者为1 或者为2 所以C错 二叉树的度可以是O 1 2 所以D错 例题选择题2 5 2 一棵三叉树中 已知度为3的结点数等于度为2的结点数 且树中叶结点的数目为13 则度为2的结点数目A 4B 2C 3D 5分析 该题主要考查多叉树逻辑结构的特点 正确答案为A 例题选择题3 5 3 对一个满二叉树 m个树枝 n个结点 深度为h 则A n h mB h m 2nC m h 1D n 2h 1分析 该题主要考查满二叉树的定义正确答案为D 例题选择题4 5 4 一棵有n个结点的k叉树 树中所有结点的度之和为A n 1B knC n2D 2n分析 该题要考查树的结点和度之间的关系由树的度的定义可知结点的度即为与之相连的子结点的个数 只有根结点不是连在其他结点上 所以和为n 1 答案为A 例题选择题5 5 5 将含有150个结点的完全二叉树从根这一层开始 每一层从左到右依次对结点进行编号 根结点的编号为1 则编号为69的结点的双亲结点的编号为A 33B 34C 35D 36分析 该题主要考查完全二叉树的逻辑结构由二叉树的性质5可知 结点69的双亲结点编号为 69 2 34 所以答案为B 例题判断题1 1 1 完全二叉树中 若一个结点没有左孩子 则它必然是叶子结点 正确分析 该题口主要考查完全二叉树的逻辑结构 深度为k的 有n个结点的二叉树 当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时 称为完全二叉树 根据此定义 若完全二叉树中某结点无左孩子 则其必定没有右孩子 因此是叶结点 所以这种说法是正确的 例题填空题1 4 1 一棵高度为H的满K叉树 按层次从1开始编号 则 1 第i层结点的数为 2 编号为n的结点的父结点的编号为 3 编号为n的结点的第i个孩子的编号为 4 编号为n的结点有右兄弟的条件是 右兄弟的编号为 分析 该题主要考查对二叉树定义和性质的理解 ki 1 k n 1 1 i n 1 例题填空题2 4 2 如果某二叉树中有30个叶结点 另有30个结点仅有一个孩子结点 则该二叉树中共有 个结点 分析 该题口主要考查二叉树结点之间的关系 设i j k分别为二叉树中度为O 1 2的结点数则n i j k 根据二叉树的性质 i k 1 有n i j i 1 30 30 30 1 89 所以二叉树中有个89结点 89 例题填空题3 4 3 n个结点的完全二叉树 编号最大的非叶结点是 号结点 编号最小的叶结点是 号结点 分析 该题主要考查完全二叉树的结构 n个结点的完全二叉树 编号最大的叶结点就是n号结点 它的双亲结点就是编号最大的非叶结点 根据完全二叉树的性质 n的双亲为 n 2 编号最大的非叶结点的右边一个结点 即 n 2 1号结点 是编号最小的叶结点 n 2 n 2 1 例题应用题4 4 4 设一棵度为k的树中有n1个度为1的结点 n2个度为2的结点 nk个度为k的结点 求该树上有多少叶子结点 分析与解答 该题主要考查树的基本概念和结构 根据两个等式 求结点总数 n n0 n1 nk求树枝总数 n 1 n1 2n2 knk因此 n0 1 0n1 1n2 k 1 nk n0 习题 一 选择题1 设树T的度为4 其中度为1 2 3 4的结点个数分别为4 2 1 1 则树T中叶子数为 A 5B 6C 7D 82 由4个结点可以构造出多少种不同的二叉树 A 10B 12C 14D 163 一颗二叉树具有10个度为2的结点 5个度为1的结点 则度为0的结点个数是 A 9B 11C 15D 不确定二 填空题1 已知二叉树有50个叶子结点 则该二叉树的总结点数至少是 99 2 在一颗二叉树中 度为0的结点的个数为n0 度为2的结点个数为n2 则有n0 N2 1 3 设一颗完全二叉树叶子结点数为k 最后一层结点数为偶数时 则该二叉树的高度为 log 2k 1 1 最后一层结点为奇数时 则该二叉树的高度为 logk 2 4 深度为k的完全二叉树至少有 2 k 1 个结点 至多有 2 k 1 个结点 习题 续 三 应用题1 已知一棵树边的集合为 i m i n e i b e b d a b g j g k c g c f h l c h a c 用树型表示法画出此树 并回答下列问题 1 哪个是根结点 2 哪些是叶结点 3 哪个是g的双亲 4 哪些是g的祖先 5 哪些是g的孩子 6 哪些是e的子孙 7 哪些是e的兄弟 哪些是f的兄弟 8 结点b和n的层次号分别是什么 9 树的深度是多少 10 以结点c为根的子树的深度是多少 11 树的度是多少 课堂练习 应用题1 若一颗二叉树中所有非叶子结点都有左右孩子 假设这颗二叉树有2009个叶子结点 则该树中共有多少结点 2 已知某完全二叉树有100个结点 则该二叉树的叶子数是多少 判断题1 二叉树是度为2的有序树 2 完全二叉树一定存在度为1的结点 3 完全二叉树一定不存在度为1的结点 4 对于有N个结点的二叉树 其高度为log2n 5 没有度为0的二叉树6 二叉树中至少有一个结点的度为2 6 3遍历二叉树和线索二叉树 遍历二叉树算法6 1先序遍历二叉树算法6 2中序遍历二叉树的非递归算法算法6 3中序遍历二叉树的非递归算法算法6 4先序创建二叉树线索二叉树算法6 5线索二叉树中序遍历算法6 6中序线索二叉树算法6 7中序线索二叉树 遍历二叉树 遍历 按一定规律走遍二叉树的各个顶点 且使每一顶点仅被访问一次 即找一个完整而有规律的走法 以得到树中所有结点的一个线性排列思路二叉树组成 左子树 根 右子树 如果能够依次遍历左子树 根和右子树这三部分 则能够遍历整个树遍历方式 根据根的访问次序 分为3种先序遍历 访问根结点 先序遍历左子树先序遍历右子树中序遍历 中序遍历左子树访问根结点中序遍历右子树后序遍历 后序遍历左子树后序遍历右子树访问根结点按层次遍历 从上到下 从左到右访问各结点 先序遍历图例 DLR 先序遍历序列 ABDC 中序遍历图例 LDR 中序遍历序列 BDAC 后序遍历图例 LRD 后序遍历序列 DBCA 遍历二叉树示例 先序遍历 中序遍历 后序遍历 层次遍历 a b c d e f a b c d e f a b c d e f a b c d e f 算法6 1先序遍历二叉树的递归算法 StatusPreOrderTraverse BiTreeT Status Visit TElemType 先序遍历采用二叉链表存储的二叉树Tif T if Visit T LChild Visit 递归遍历左子树if PreOrderTraverse T RChild Visit reutrnOK 递归遍历右子树reutrnERROR elsereturnOK PreOrderTraverse StatusPrintElem TElemTypee printf e 调用 ProOrderTraverse T PrintElement 中序 后序遍历二叉树的递归算法 StatusInOrderTraverse BiTreeT Status Visit TElemType if T if InOrderTraverse T LChild Visit if Visit T RChild Visit reutrnOK reutrnERROR elsereturnOK InOrderTraverseStatusPostOrderTraverse BiTreeT Status Visit TElemType if T if PostOrderTraverse T LChild Visit if PostOrderTraverse T RChild Visit if Visit T data reutrnOK reutrnERROR elsereturnOK PostOrderTraverse 递归遍历的过程示意 先序遍历 abc 中序遍历 a b c 后序遍历 ab c 先序调用过程示意图 if T Visit T data pre T lchild pre T rchild 返回 返回 返回 返回 A C B D 返回 先序序列 ABDC 算法6 2中序遍历二叉树非递归算法1 StatusInOrderTraverse BitTreeT Status Visit TElemTypee InitStack S Push S T while Stack S while GetTop S p InOrderTraverse 算法6 3中序遍历二叉树非递归算法2 StatusInOrderTraverse BitTreeT Status Visit TElemTypee InitStack S p T while p StackEmpty S if p Push S p p p lchild ifelse Pop S p if Visit p data reutrnERROR p p rchild else whilereturnOK InOrderTraverse 遍历算法应用算法6 4CreateBiTree 按先序遍历序列建立二叉树的二叉链表 已知先序序列为 ABC DE G F StatusCreateBiTree BiTree else CreateBiTree 遍历算法应用 统计二叉树中叶子结点个数算法求二叉树深度算法 6 3 2线索二叉树 定义 前驱与后继 在二叉树的先序 中序或后序遍历序列中两个相邻的结点互称为前驱与后继线索 指向前驱或后继结点的指针称为线索线索二叉树 加上线索的二叉链表表示的二叉树叫线索二叉树线索化 对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化实现在有n个结点的二叉链表中必定有n 1个空链域在线索二叉树的结点中增加两个标志域Ltag和Rtaglchild 若LTag 0 指向左孩子 若Ltag 1 指向其前驱rchild 若RTag 0 指向右孩子 若Rtag 1 指向其后继结点定义 线索二叉树图例 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 线索二叉树图例 线索二叉树遍历 在线索树上进行遍历 只要找到序列中的第一个结点 然后依次找结点的后继直到其后继为空为止 如何找后继 不是每个结点都记录了后继的 中序线索二叉树如果对应的TAG 1 则直接得到该结点的前驱或后继 否则 结点的后继 右子树遍历的第一个结点 即右子树最左下结点结点的前驱 左子树遍历的最后一个结点 即左子树最右下结点 后序线索二叉树若结点为二叉树的根 后继为空 若结点是其双亲的右孩子或是其双亲的独生左孩子 后期为该结点的双亲若结点是其双亲的左孩子 且有右兄弟 则后继为双亲右子树上按后序遍历的第一个结点 二叉树的二叉线索存储 typedefenumPointerTag Link Thread typedefstructBiTNode TElemTypedata structBiThrNode lchild rchild PointerTagLTag RTag BiThrNode BiThrTree 算法6 5中序遍历线索二叉树 StatusInOrderTraverse Thr BiThrTreeT Status Visit TElemTypee p T lchild while p T while p LTag Link p p lchild if visit p data returnERROR while p RTag Thread InOrderTraverse Thr 二叉树的线索化算法 StatusInOrderThreading BiThrTree InThreading 例题选择题1 5 1 设n m为一棵二叉树上的两个结点 在中序遍历时 n在m之前的条件是A n在m右方B n是m祖先C n在m左方D n是m子孙分析 该题主要考查二叉树的遍历 根据二叉树的形态和中序遍历算法 当n在m左边时 结点n首先被遍历 当n是m祖先时 它们之间的关系无法确定 不妨假设n是根结点 m是其左孩子 则m在n之前 m是其右孩子 则n在m之前 正确答案为C 例题选择题2 5 2 在一棵二叉树结点的先序序列 中序序列 后序序列中 所有叶子结点的先后顺序A 都不相同B 先序和中序相同 而与后序不同C 完全相同D 中序和后序相同 而与先序不同分析 该题主要考查二叉树的遍历 无论哪种遍历所得的序列都是在 左 右 两结点的空隙中插入 根 结点的排列 即左 右结点的顺序固定不变 改变的是 根 结点 叶子结点的先后顺序都不变 答案为C 例题选择题3 5 3 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构 最佳方案是二叉树采用存储结构 A 三叉链表B 广义表C 二叉链表D 顺序分析 该题主要考查二叉树的存储结构和非递归遍历算法 此题答案为A 三叉链表是将双亲表示法和孩子兄弟表示法结合起来 既能方便地从双亲查找孩子 又能方便地从孩子查找 例题选择题4 5 4 一棵二叉树满足下列条件 对任一结点 若存在左 右子树 则其值都小于它的左子树上所有结点的值 而大于右子树上所有结点的值 现采用遍历方式就可以得到这棵二又树上所有结点的递减序列 A 先序B 中序C 后序D 层次分析 该题主要考查二叉树的遍历 由于中序遍历的顺序是先中序遍历左子树 再访问根结点 最后中序遍历右子树 这样可以保证 对任一结点其左孩子总在它的左边 其右孩子总在它的右边 当二叉树满足题述条件时 其中序序列一定是个递减序列 答案为B 例题选择题5 5 5 对含有几个结点的非空二叉树 采用任何一种遍历方式 其结点访问序列均相同 A 0B 1C 2D 不存在这样的二叉树分析 该题主要考查二叉树的三种遍历次序的关系 三种遍历方式的不同点 在于访问根结点的时机不同 当一棵二叉树仅含一个根结点时 不管采用哪种遍历方式 所得到的结点序列总是相同的 此题答案为B 例题判断题1 4 1 按中序遍历二叉树时 某个结点 有右子树 的直接后继是它的右子树中第一个被访问的结点 正确分析 该题主要考查二叉树的中序遍历 这种说法正确 因为中序遍历按LDR的顺序进行 若以某结点为其直接后继 必须是右子树中第一个被访问的结点 例题判断题2 4 2 有1个以上结点的二叉树 已知先序和后序遍历序列 能唯一确定一棵二叉树 错误分析 该题主要考查二叉树的遍历的性质 这种说法不正确 如已知先序为12 后序遍历为21 则可以有两棵二叉树 例题判断题3 5 3 用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历 正确分析 该题主要考查二叉树的遍历和逻辑结构 用二叉树的先序遍历和中序遍历可以确定二叉树的逻辑结构 就可以进一步导出二叉树的后序遍历 通常已知二叉树的先序遍历和后序遍历 无法确定一棵二叉树 例题判断题4 4 4 若一个叶子结点是某二叉树中序遍历序列的最后一个结点 那么它也是该二叉树的先序遍历序列的最后一个结点 正确分析 该题主要考查二叉树的遍历 当一个叶子结点是某二叉树中序遍历的最后一个结点 则它一定位于二叉树的右子树上最右端 无论先序遍历或中序遍历 右子树上的最右端的叶子结点肯定最后访问 若题中的叶子结点替换成普通结点 则命题不成立 例题填空题 1 N个结点的二叉树按某种遍历规则对结点从1到N依次递增编号 如果 1 任一结点的编号等于它的左子树中的最小编号减1 则为 遍历 2 某结点右子树中最小编号等于左子树中的最大编号加1 则为 遍历 答案 先序 后序 分析 该题主要考查二叉树的结构和遍历 对于先序遍历 因为首先访问根结点 再先序遍历左子树 最后先序遍历右子树 所以根结点编号等于左子树的根结点编号减1 对于后序遍历 因为首先后序遍历左子树 然后后序遍历右子树 最后访问根结点 所以右子树中最小编号等于左子树中的最大编号加1 例题应用题1 2 1 满足下列条件的非空二叉树具有什么形状 1 先序和中序相同 2 中序和后序相同 3 先序和后序相同分析 该题主要考察二叉树的结构和遍历性质 1 只有一个结点或没有左子树的二叉树 2 只有一个结点或没有右子树的二叉树 3 只有一个结点的二叉树 例题应用题2 2 2 已知二叉树左右子树都含有m个结点 当m鹅时 试构造满足如下要求的所有二叉树 1 左右子树的先序与中序序列相同 2 左子树的中序与后序序列相同 右子树的先序与中序序列相同 分析 该题由上题引中得到 主要考查二叉树的结构和遍历的性质如图 例题算法设计题 设两棵二叉树的根结点地址分别为P及Q 采用二叉链表的形式存储这二棵树上所有的结点 请编写程序 判断它们是否相似 分析 该题主要考查二叉树遍历算法的应用 所谓二棵二叉树S和t相似 要求 它们都为空或都只有一个根结点 或它们的根结点及左右子树均相似 StatusBiLike BiTreeP BiTreeQ if P NULL BiLike 习题 填空题1 某二叉树的先序遍历序列和后序遍历序列正好相反 则此二叉树一定是 A 空或只有一个结点B 完全二叉树C 单支树D 高度等于结点数2 在二叉树结点的先序序列 中序序列和后序序列中 所有叶子结点的先后顺序 A 都不相同B 完全相同C 先序和中序相同 而与后序不同D 中序和后序相同 而与先序不同填空题1 有 种不同形态的二叉树可以按照中序遍历得到相同的abc序列 2 已知二叉树先序为ABDEGCF 中序为DBGEACF 则后序一定是 判断题1 二叉树线索化后一定不存在空指针域 2 非空的二叉树一定满足 某结点若有左孩子 则其中序前驱一定没有右孩子 3 由先序和后序遍历序列不能唯一确定一棵二叉树 4 一个树的叶结点 在前序遍历和后序遍历下 皆以相同的相对位置出现 算法设计题1 设计一个将二叉树中每个结点的左右孩子互换的算法 2 试编写算法判断两棵二叉树是否等价 称二叉树T1和T2是等价的 如果T1和T2都是空的二叉树 或者T1和T2的根结点的值相同 并且T1的左子树与T2的左子树是等价的 T1的右子树与T2的右子树是等价的 课堂练习 假设一棵二叉树的层次序列是ABCDEFGHIJ和中序序列是DBGEHJACIF 请画出该树 6 4树和森林 树的存储结构森林和二叉树的转换树和森林的遍历 树的存储结构 双亲表示法 双亲表示法以一组地址连续空间存储树的结点 同时在每个节点中附设一个指示器指示其双亲节点在链表中的位置 defineMAX TREE SIZE100typedefstructPTNode 结点结构TElemTypedata intparent 双亲位置域 PTNode typedefstruct 树结构PTNodenodes MAX TREE SIZE intr n 根的位置和结点数 PTree利用除了根以外每个结点有唯一的双亲的特点 0 1 2 2 3 5 5 5 1 可以方便地找某个结点的双亲 如何找某个结点的孩子 树的存储结构 多重链表 思路多重链表 每个结点有多个指针域 分别指向其子树的根结点同构 结点的指针个数相等 为树的度D结点不同构 结点指针个数不等 为该结点的度d分析同构方案 有大量空指针域异构方案 操作不方便 树的存储结构 孩子表示法 孩子链表 每个结点的孩子结点用单链表存储 再用含n个元素的结构数组指向每个孩子链表树的孩子链表存储表示typedefstructCTNode intchild 该结点在表头数组中下标structCTNode next 指向下一孩子结点 ChildPtr typedefstruct TELemTypedata 数据域ChildPtr firstchild 指向第一个孩子结点 CTBox typedefstruct CTBoxnode MAX TREE SIZE intn r CTree 如何找双亲结点 孩子链表 带双亲的孩子链表 孩子兄弟表示法 二叉树表示法 用二叉链表作树的存储结构 链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点typedefstructCSNode TElemTypedata structnode firstchild nextsibling CSNode CSTree 特点 操作容易 破坏了树的层次 森林与二叉树的转换 由于树和二叉树都可以用二叉链表作为存储结构 则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系同样可以导出森林与二叉树的对应关系 树与二叉树对应 森林与二叉树的对应 将树根相连 树转换成的二叉树其右子树一定为空 将树转换成二叉树 加线 在兄弟之间加一连线抹线 对每个结点 除了其左孩子外 去除其与其余孩子之间的关系旋转 以树的根结点为轴心 将整树顺时针转45 将二叉树转换成树 加线 若p结点是双亲结点的左孩子 则将p的右孩子 右孩子的右孩子 沿分支找到的所有右孩子 都与p的双亲用线连起来抹线 抹掉原二叉树中双亲与右孩子之间的连线调整 将结点按层次排列 形成树结构 森林转换成二叉树 将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根 再以根结点为轴心 顺时针旋转 构成二叉树型结构 二叉树转换成森林 抹线 将二叉树中根结点与其右孩子连线 及沿右分支搜索到的所有右孩子间连线全部抹掉 使之变成孤立的二叉树还原 将孤立的二叉树还原成树 森林转换为二叉树的形式定义 如果F T1 T2 Tm 是森林 则可按如下规则转换成一棵二叉树B root LB RB 若F为空 即m 0 则B为空树若F非空 即m 0 则B的根root为森林中第一颗树的根ROOT T1 B的左子树LB是从T1中根结点的子树森林F1 T11 T12 T1m1 转换而成的二叉树B的右子树RB是从森林F1 T2 T3 Tm 转换而成的二叉树 二叉树转换为森林的形式定义 如果B root LB RB 是一棵二叉树 则可按如下规则转换成森林F T1 T2 Tm 若B为空 则F为空若B非空 则F中第一颗树T1的根ROOT T1 即为二叉树B的根root T1中根结点的子树森林F1是由B的左子树LB转换而成的森林F中除T1外其余的树组成的森林F T2 T3 Tm 是由B的右子树RB转换而成的森林 树和森林的遍历 树的遍历先根 序 遍历 先访问树的根结点 然后依次先根遍历根的每棵子树后根 序 遍历 先依次后根遍历每棵子树 然后访问根结点按层次遍历 先访问第一层上的结点 然后依次遍历第二层 第n层的结点森林的遍历先序遍历森林访问森林中第一颗树的根结点先序遍历第一颗树中根结点的子树森林先序遍历除去第一颗树之后剩余的树构成的森林中序遍历森林中序遍历森林中第一颗树的根结点的子树森林访问第一颗树的根结点中序遍历除去第一颗树之后剩余的树构成的森林 遍历的关系 当森林转换为二叉树时森林的先序和中序遍历等于对应的二叉树的先序和中序遍历当以二叉链表作为树的存储结构时树的先根遍历和后根遍历可借用二叉树的先序遍历和中序比那里的算法实现 例题选择题1 3 设X是树T中的一个非根结点 B是T所对应得二叉树 在B中 X是其双亲的右孩子 下列结论正确的是A 在树T中 X是其双亲的第一个孩子 B 在树T中 X一定无右边兄弟 C 在树T中 X一定是叶子结点 D 在树T中 X一定有左边兄弟 分析 该题口主要考查树和二叉树的转换 根据树和二叉树转换的规则可以得到D为正确答案 例题选择题2 3 设森林中有3棵树 其中第1 第2和第3棵树的结点个数分别为n1 n2 n3 则与森林对应的二叉树中根结点的右子树上的结点个数是A n1B n1 n2C n3D n2 n3分析 该题主要考查森林和二叉树之间的转换关系 森林中的第一棵树对应于二叉树根结点及其左子树 第2和第3棵树对应于二叉树中根结点的右子树 则其结点个数为n2 n3 答案为D 例题选择题3 3 树的先根序列和其对应的二叉树的是一样的 树的后根序列和其对应的二叉树的是一样的 A 先序序列B 中序序列C 后序序列D 按层次遍历序列分析该题主要考查树和二叉树的转换关系 考虑树的根结点及其n个子树 当转换为二叉树后 根结点和最左子树的根结点的位置不变 而其它子树的根结点都成为其相邻左子树根结点的右孩子 这样的转换是递归过程 观察这样的结构变化 答案为A B 例题判断题1 1 将一棵树转换成二叉树后 根结点没有左子树 错误分析 该题主要考查树和二叉树的转换 树转换成二叉树满足 左孩子 右兄弟 规则 只有当树结点个数为1时 树转换成二叉树后 根结点没有左子树 例题填空题 1 森林T转化为二叉树B B中某结点在森林中为叶子结点的条件为 B中左子树为空的结点分析 该题主要考查森林和二叉树的转化 当B中左子树为空时 意味着该结点没有孩子结点 设F是一个森林 B是由F转换得到的二叉树 F中有n个非终端结点 则B中右指针域空的结点有个 n 1分析该题主要考查森林和二叉树的转化 例题应用题1 2 将该树转换为二叉树 例题应用题2 2 求各树的先根序列和后根序列求森林的先序和后序序列 ABCDEFGHIJKLMPQRNOBDEFCAIJKHGQRPMNOLABCDEFGHIJKLMPQRNOBDEFCAIJKHGQRPMNOL 习题 填空题1 如果T1是由树T转换而来的二叉树 那么对T中结点的后序遍历就是对T1中结点的遍历 2 树在计算机内的存储结构有 和 应用题将该森林转换为二叉树 6 6哈夫曼树及其应用 最优二叉树 哈夫曼树 哈夫曼编码算法6 12算法6 13 哈夫曼编码实例 最优二叉树 从树的一个结点到另一个结点之间的分支构成两个结点之间的路径路径上的分支数称为路径长度从树根到每一个结点的路径长度之和称为树的路径长度完全二叉树是路径长度最短的二叉树结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积树的带权路径长度为树中所有叶子结点的带权路径长度之和 记为WPLWPL最小的二叉树称为最优二叉树或哈夫曼树 具有不同带权路径长度的二叉树 4个叶子结点a b c d 分别带权7 5 2 4 它们的带权路径长度计算 a WPL 7x2 5x2 2x2 4x2 36 b WPL 7x3 5x3 2x1 4x2 46 c WPL 7x1 5x2 2x3 4x3 35 最优二叉树应用之一 用哈夫曼树可以得到判定问题的最佳判定算法 构造哈夫曼树 哈夫曼算法根据给定的n个权值 w1 s2 wn 构成n颗二叉树的集合F T1 T2 Tn 其中每颗二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 在F中选取两颗根结点的权值最小的树作为左右子树构造一颗新的二叉树 且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和 在F中删除这两颗树 同时将新得到的二叉树插入F中重复以上两步 直到F只含一颗树为止 即哈夫曼树 例w 5 29 7 8 14 23 3 11 Huffman树应用最佳判定树 编码思想 前缀编码任何一个字符的编码都不是另一个字符的编码的前缀的编码方案利用二叉树可以实现前缀编码从根到叶子的路径即为叶子所对应字符的编码如何设计可以使得电文总长度最短的二进制前缀编码 出现频率越高的字符的路径越短 反之路径越长 思想 根据字符出现频率编码 使电文总长最短编码 根据字符出现频率构造Huffman树 然后将树中结点引向其左孩子的分支标 0 引向其右孩子的分支标 1 每个字符的编码即为从根到每个叶子的路径上得到的0 1序列例 要传输的字符集D C A S T 字符出现频率w 2 4 2 3 3 译码 从Huffman树根开始 从待译码电文中逐位取码 若编码是 0 则向左走 若编码是 1 则向右走 一旦到达叶子结点 则译出一个字符 再重新从根出发 直到电文结束 例电文是 CAS CAT SAT AT 其编码 11010111011101000011111000011000 电文为 1101000 译文只能是 CAT T 00 01A 10C 110S 111 Huffman编码 数据通信用的二进制编码 算法6 12求哈夫曼编码的算法之存储结构 思想哈夫曼树没有度为1的结点 严格的二叉树 正则二叉树 对于一个有n的