第5章 树与二叉树(java版).pptVIP

第五章树与二叉树 教学内容 5 2二叉树的基本概念 5 1树的基本概念 5 4哈夫曼树及哈夫曼编码 5 3二叉树的遍历 5 5树与森林 教学重点与难点 重点 二叉树的性质 二叉树的存储方法二叉树的遍历及其应用哈夫曼编码 难点 二叉树遍历算法的应用 课前思考 你见过家族谱系图吗 试以图形表示从你的祖父起的家族成员关系 这类图形正是本章要讨论的 树 结构 5 1 1树的定义 5 1 2树的常用术语 5 1树的基本概念 5 1 1树的定义 树是由n n 0 个结点所构成的有限集合 当n 0时 称为空树 当n 0时 n个结点满足以下条件 有且仅有一个称为根的结点 其余结点可分为m m 0 个互不相交的有限集合 且每一个集合又构成一棵树 这棵树称为是根结点的子树 5 1 1树的定义 例如 root T1 T2 T3 5 1 1树的定义 树的表示方法 树形表示法 文氏图表示法 凹入图表示法 广义表 括号 表示法 5 1 1树的定义 5 1 1树的定义 5 1 1树的定义 线性结构 树型结构 第一个数据元素 无前驱 存在一个根结点 无前驱 最后一个数据元素 无后继 存在多个叶子结点 无后继 其它数据元素 一个前驱 一个后继 其它结点 一个前驱 双亲 多个后继 孩子 元素之间存在 一对一 的关系 元素之间存在 一对多 的关系 5 1 1树的定义 5 1 2树的常用术语 5 1树的基本概念 5 1 2树的常用术语 结点 结点的度 树的度 叶子结点 分支结点 数据元素 所有关联子树根的分支 结点所拥有子树的数目 树中所有结点的度的最大值 度为零的结点 度大于零的结点 分支 根和子树根之间的连线 边 结点的路径 由从根到该结点所经分支和结点构成 孩子结点 双亲结点兄弟结点 堂兄弟祖先结点 子孙结点 结点的层次 树的深度 树中所有结点层次数的最大值加1 假设根结点的层次为0 则其它结点的层次是其双亲结点的层次数加1 有序树 树中各结点的所有子树之间从左到右有严格的次序关系 无序树 森林 由m m 0 棵互不相交的树所构成的集合 与有序树相反 无序树是指树中各结点的所有子树之间没有严格的次序关系 5 2 1二叉树的定义 5 2 2二叉树的性质 5 2 3二叉树的存储结构 5 2二叉树的基本概念 5 2 1二叉树的定义 二叉树或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不交的二叉树组成 根结点 左子树 右子树 5 2 1二叉树的定义 二叉树的五种基本形态 N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子树均不为空树 5 2 1二叉树的定义 具有3个结点的树与二叉树的形态各有多少种 树有2种而二叉树有5种 问 二叉树就是度小于等于2的树 这个结论是否正确 满二叉树的定义 如果在一棵二叉树中 它的所有结点或者是叶结点 或者是左 右子树都非空 并且所有叶结点都在同一层上 则称这棵二叉树为满二叉树 完全二叉树的定义 如果在一棵具有n个结点的二叉树中 它的逻辑结构与满二叉树的前n个结点的逻辑结构相同 则称这样的二叉树为完全二叉树 完全二叉树 非完全二叉树 单分支树的定义 左支树 左支树 右支树 右支树 所有结点都没有右孩子的二叉树 所有结点都没有左孩子的二叉树 5 2 1二叉树的定义 5 2 2二叉树的性质 5 2 3二叉树的存储结构 5 2二叉树的基本概念 5 2 2二叉树的性质 在二叉树的第i层上至多有2i个结点 i 0 用归纳法证明 归纳基 归纳假设 归纳证明 i 0层时 只有一个根结点 20 1 假设对所有的j 0 j i 层 命题成立 则第i层的结点数 2i 1 2 2i 性质1 5 2 2二叉树的性质 深度为h h 1 的二叉树上至多含2h 1个结点 性质2 证明 基于上一条性质 深度为h的二叉树上的结点数至多为 20 21 2h 1 2h 1 5 2 2二叉树的性质 对于任何一棵二叉树 若其叶结点的个数为n0 度为2的结点个数为n2 则有n0 n2 1 性质3 则二叉树上结点总数n 二叉树上分支总数e n0 n1 n2 而e与n的关系如何 证明 n1 2n2 由此得 n0 n2 1 设度为1的结点数为n1 e n 1 5 2 2二叉树的性质 度为m的树中 叶子结点数与其它结点数之间的关系如何 思考 5 2 2二叉树的性质 具有n个结点的完全二叉树的深度为 log2n 1或 log2 n 1 性质4 证明 设完全二叉树的深度为h 则根据第二条性质得 2h 1 1 n 2h 1 即2h 1 n 2h h 1 log2n h 因为h只能是整数 因此 h log2n 1 推出 5 2 2二叉树的性质 性质5 若对含n个结点的完全二叉树从上到下且从左至右进行0至n 1的编号 则对完全二叉树中任意一个编号为i的结点 有 1 若i 0 则该结点是二叉树的根 无双亲 否则 编号为 i 1 2 的结点为其双亲结点 2 若2i 1 n 则该结点无左孩子 否则 编号为2i 1的结点为其左孩子结点 3 若2i 2 n 则该结点无右孩子结点 否则 编号为2i 2的结点为其右孩子结点 5 2 1二叉树的定义 5 2 2二叉树的性质 5 2 3二叉树的存储结构 5 2二叉树的基本概念 5 2 3二叉树的存储结构 2 二叉树的链式存储结构 1 二叉树的顺序存储结构 5 2 3二叉树的存储结构 顺序存储 用一组地址连续的存储单元从根结点开始依次自上而下 并按层次从左到右存储完全二叉树上的各结点元素 即将完全二叉树编号为i的结点元素存储在下标为i数组元素中 对于完全二叉树 5 2 3二叉树的存储结构 顺序存储 例如 完全二叉树 5 2 3二叉树的存储结构 顺序存储 先在树中增加一些并不存在的虚结点并使其成为一棵完全二叉树 然后用与完全二叉树相同的方法对结点进行编号 再将编号为i的结点的值存放到数组下标为i的数组单元中 虚结点不存放任何值 对于非完全二叉树 5 2 3二叉树的存储结构 顺序存储 例如 非完全二叉树 问 一个深度为k且只有k个结点的右支树需要的数组存储单元为多少 顺序存储仅适用于满或完全二叉树 5 2 3二叉树的存储结构 链式存储 1 二叉链表 2 三叉链表 5 2 3二叉树的存储结构 二叉链表 root 结点结构 5 2 3二叉树的存储结构 三叉链表 结点结构 5 2 3二叉树的存储结构 二叉链表 二叉链表中结点类的描述 书中P156 publicclassBiTreeNode 构造一个空结点publicBiTreeNode this null 构造一个左 右孩子域为空的结点publicBiTreeNode Objectdata this data null null privateObjectdata 结点的数据域privateBiTreeNodelchild rchild 左 右孩子域 5 2 3二叉树的存储结构 二叉链表 二叉链表中结点类的描述 书中P156 publicclassBiTreeNode 构造一个数据域和左 右孩子域都不为空的结点publicBiTreeNode Objectdata BiTreeNodelchild BiTreeNoderchild this data data this lchild lchild this rchild rchild 5 2 3二叉树的存储结构 二叉链表 二叉链表存储结构下二叉树类的描述 书中P158 publicclassBiTree 构造一棵空树publicBiTree this root null 构造一棵根结点为root的树publicBiTree BiTreeNoderoot this root root privateBiTreeNoderoot 树的根结点 5 3 1二叉树的遍历方法及其实现 5 3 2二叉树遍历算法的应用举例 5 3 3建立二叉树 5 3二叉树的遍历 5 3 1二叉树的遍历方法及其实现 一 问题的提出 二 二叉树遍历方法及其递归实现 三 二叉树遍历方法的非递归实现 5 3 1二叉树的遍历方法及其实现 沿着某一条搜索路径对二叉树中的结点进行访问 使得每个结点均被访问一次 而且仅被访问一次 一 问题的提出 访问 的含义可以很广 如 输出结点的信息等 什么是遍历 5 3 1二叉树的遍历方法及其实现 一 问题的提出 遍历 是任何类型均有的操作 对线性结构而言 只有一条搜索路径 因为每个结点均只有一个后继 故不需要另加讨论 而二叉树是非线性结构 每个结点有两个后继 则存在如何遍历即按什么样的搜索路径遍历的问题 5 3 1二叉树的遍历方法及其实现 一 问题的提出 二 二叉树遍历方法及其递归实现 三 二叉树遍历方法的非递归实现 5 3 2二叉树的遍历方法及其实现 二 二叉树的遍历方法及递归实现 对 二叉树 而言 可以有三条搜索路径 1 先上后下的遍历 2 先左后右的遍历 3 先右后左的遍历 5 3 1二叉树的遍历方法及其实现 二叉树的遍历方法 对应三条搜索路径 二叉树 有7种遍历方法 1 层次遍历方法 2 DLR 先根遍历 LDR 中根遍历 LRD 后根遍历 3 DRL RDL RLD 5 3 1二叉树的遍历方法及其实现 1 层次遍历 若二叉树为空 则为空操作 否则 按自上而下先访问第0层的根结点 然后再从左到右依次访问各层次中的每一个结点 层次遍历序列 ABECFDGHK 5 3 1二叉树的遍历方法及其实现 2 先根 序 遍历 DLR 定义及递归实现 若二叉树为空树 则空操作 否则 1 访问根结点 2 先根遍历左子树 3 先根遍历右子树 先根遍历序列 ABCDEFGHK 先根遍历序列 ABCDEFGHK publicvoidpreRootTraverse BiTreeNodeT 先根遍历操作实现的递归算法描述 5 3 1二叉树的遍历方法及其实现 if T null System out print T getData preRootTraverse T getLchild preRootTraverse T getRchild 5 3 1二叉树的遍历方法及其实现 3 中根 序 遍历 LDR 定义及递归实现 若二叉树为空树 则空操作 否则 1 中根遍历左子树 2 访问根结点 3 中根遍历右子树 动画播放 6 4 2 2 中根遍历序列 BDCQEHGKF 中根遍历序列 BDCAEHGKF publicvoidintRootTraverse BiTreeNodeT 中根遍历操作实现的递归算法描述 5 3 1二叉树的遍历方法及其实现 if T null System out print T getData intRootTraverse T getLchild intRootTraverse T getRchild 5 3 1二叉树的遍历方法及其实现 4 后根 序 遍历 LRD 定义及递归实现 若二叉树为空树 则空操作 否则 1 后根遍历左子树 2 后根遍历右子树 3 访问根结点 动画播放 6 4 2 3 后根遍历序列 DCBHKGFE 后根遍历序列 DCBHKGFEA publicvoidpostRootTraverse BiTreeNodeT 后根遍历操作实现的递归算法描述 5 3 1二叉树的遍历方法及其实现 if T null System out print T getData postRootTraverse T getLchild postRootTraverse T getRchild 5 3 1二叉树的遍历方法及其实现 一 问题的提出 二 二叉树遍历方法及其递归实现 三 二叉树遍历方法的非递归实现 5 3 1二叉树的遍历方法及其实现 1 先根遍历操作的非递归实现 方法 借助一个栈来记载当前被访问结点的右孩子结点 主要思想 从非空二叉树的根结点出发 沿着该结点的左子树向下搜索 在搜索过程中每遇到一个结点就先访问该结点 并将该结点的非空右孩子结点压栈 当左子树结点访问完成后 从栈顶弹出结点的右孩子结点 然后用上述同样的方法去遍历该结点的右子树 依此类推 直到二叉树中所有的结点都被访问为止 5 3 1二叉树的遍历方法及其实现 1 先根遍历操作的非递归实现 基本步骤 创建一个栈对象 根结点入栈 当栈为非空时 将栈顶结点弹出栈内并访问该结点 LinkStackS newLinkStack T BiTreeNode S pop S push T System out print T getData 5 3 1二叉树的遍历方法及其实现 1 先根遍历操作的非递归实现 基本步骤 对当前访问结点的非空左孩子结点相继依次访问 并将当前访问结点的非空右孩子结点压入栈内 重复执行步骤 和 直到栈为空为止 While T null if T getLchild null System out print T getData if T getRchild null S push T getRchild T T getLchild 先根遍历的非递归算法 书P161算法5 4 LinkStackS newLinkStack T BiTreeNode S pop S push T System out print T getData while T null if T getLchild null System out print T getData if T getRchild null S push T getRchild T T getLchild while S isEmpty publicvoidpreRootTraverse BiTreeNodeT root if T null 时间复杂度 O n 5 3 1二叉树的遍历方法及其实现 2 中根遍历操作的非递归实现 方法 借助一个栈来记载遍历截长过程中所经历的而未被访问的所有结点 主要思想 从非空二叉树的根结点出发 沿着该结点的左子树向下搜索 在搜索过程中将所遇到的每一个结点依次压栈 直到二叉树中最左下的结点压栈为止 然后从栈中弹出栈顶结点并对其进行访问 访问完后再进入该结点的右子树并用上述同样的方法去遍历该结点的右子树 依此类推 直到二叉树中所有的结点都被访问为止 5 3 1二叉树的遍历方法及其实现 2 中根遍历操作的非递归实现 基本步骤 创建一个栈对象 根结点入栈 若栈顶结点非空 则将栈顶结点的非空左孩子相继进栈 LinkStackS newLinkStack while S peek null S push T S push BiTreeNode S peek getLchild S pop 空结点出栈 5 3 1二叉树的遍历方法及其实现 2 中根遍历操作的非递归实现 基本步骤 栈顶结点出栈并访问非空栈顶结点 再使该栈顶结点的非空右孩子结点入栈 重复执行步骤 和 直到栈为空为止 if S isEmpty T BiTreeNode S pop System out print T getData S push T getRchild 中根遍历的非递归算法 书P162算法5 5 LinkStackS newLinkStack S push T while S isEmpty publicvoidinRootTraverse BiTreeNodeT root if T null while S peek null S push BiTreeNode S peek getLchild S pop if S isEmpty T BiTreeNode S pop System out print T getData S push T getRchild 时间复杂度 O n 5 3 1二叉树的遍历方法及其实现 3 后根遍历操作的非递归实现 方法 借助一个栈来记载遍历截长过程中所经历的而未被访问的所有结点 引进一个访问标志变量flag和一个结点指针p 其中 flag用来标记当前栈顶结点是否被访问 当值为true时 表示栈顶结点已被访问 当值为false时 表示当前栈顶结点未被访问 指针p指向当前遍历过程中最后一个被访问的结点 5 3 1二叉树的遍历方法及其实现 3 后根遍历操作的非递归实现 基本步骤 创建一个栈对象 根结点入栈 p赋初始值null 若栈顶结点非空 则将栈顶结点的非空左孩子相继进栈 LinkStackS newLinkStack while S peek null S push T S push BiTreeNode S peek getLchild S pop BiTreeNOdep null 若栈非空 查看栈顶结点 若栈顶结点的右孩子为空 或者与p相等 则将栈顶结点弹出栈并访问它 同时使p指向该结点 并置flag值为true 否则 将栈顶结点的右孩子压入栈 并置flag值为false if T getRchild null T getRchild p else System out print T getData S push T getRchild T BiTreeNode S pop p T flag true flag flase 5 3 1二叉树的遍历方法及其实现 3 后根遍历操作的非递归实现 基本步骤 若flag值为true 则重复执行步骤 否则 重复执行步骤 和 直到栈为空为止 while S isEmpty while S isEmpty if flag break 后根遍历的非递归算法 书P163算法5 6 publicvoidpostRootTraverse BiTreeNodeT root if T null while S isEmpty while S isEmpty if flag break 时间复杂度 O n 5 3 1二叉树的遍历方法及其实现 4 层次遍历操作的非递归实现 方法 借助一个队列 在遍历开始时 首先将根结点入队 然后每次从队列中取出队首元素进行处理 每处理一个结点 都是先访问该结点 再按从左到右的顺序把它的孩子结点依次入队 5 3 1二叉树的遍历方法及其实现 4 层次遍历操作的非递归实现 基本步骤 创建一个链队列对象 根结点入队 LinkStackL newLinkQueue L offer T 5 3 1二叉树的遍历方法及其实现 4 层次遍历操作的非递归实现 基本步骤 若队列非空 重复将队首结点出队并访问该结点 再将该结点的非空左 右孩子结点依次入队 直到队列为空为止 while L isEmpty T BiTreeNode L poll System out print T getData if T getLchild null L offer T getLchild if T getRchild null L offer T getRchild 层次遍历的非递归算法 书P166算法5 7 publicvoidlevelTraverse BiTreeNodeT root if T null LinkStackL newLinkQueue L offer T while L isEmpty T BiTreeNode L poll System out print T getData if T getLchild null L offer T getLchild if T getRchild null L offer T getRchild 时间复杂度 O n 5 3 1二叉树的遍历方法及其实现 5 3 2二叉树遍历算法的应用举例 5 3 3建立二叉树 5 3二叉树的遍历 5 3 2二叉树的遍历应用举例 1 在二叉树上的查找某个结点 2 计算二叉树中结点的个数 3 求二叉树的深度 4 判断两棵二叉树是否相等 1 在二叉树上的查找某个结点 要求 实现方法 在以T为根结点的二叉树中查找值为x的结点 若找到 则返回该结点 否则 返回空值 可在先根遍历过程中进行查找 并将先根遍历算法中的 访问结点 的操作改为 将根结点的值与x进行比较的操作 1 在二叉树上的查找某个结点 实现步骤 1 若二叉树为空 则不存在这个结点 返回空值 否则 将根结点的值与x进行比较 若相等 则返回该结点 2 否则在左子树中进行查找 若找到 则返回找到的结点 3 否则返回在右子树中进行查找的结果 1 在二叉树上的查找某个结点 实现算法 书P166算法5 8 publicBiTreeNodesearchNode BiTreeNodeT Objectx if T null if T getData equals x returnT else BiTreeNodelresult searchNOde T getLchild x returnlresult null lresult searchNOde T getRchild x 5 3 2二叉树的遍历应用举例 1 在二叉树上的查找某个结点 2 计算二叉树中结点的个数 3 求二叉树的深度 4 判断两棵二叉树是否相等 要求 实现方法 计算以T为根结点的二叉树中所含结点的个数 并返回其值 由于二叉树中结点的个数等于1个根结点再分别加上它的左 右子树中结点的个数 所以可以运用不同的遍历递归算法的思想来统计出二叉树中结点的个数 2 计算二叉树中结点的个数 实现步骤 以中根遍历为例 1 引进计数变量count并赋初值0 2 若二叉树非空 则 3 返回count值 统计根结点的左子树的结点个数 并加入到count变量中 count值加1 统计根结点的右子树的结点个数 并加入到count变量中 2 计算二叉树中结点的个数 实现算法 参看书P167算法5 9 publicintcountNode BiTreeNodeT if T null count countNode T getLchild count count countNode T getRchild 2 计算二叉树中结点的个数 intcount 0 returncount 5 3 2二叉树的遍历应用举例 1 在二叉树上的查找某个结点 2 计算二叉树中结点的个数 3 求二叉树的深度 4 判断两棵二叉树是否相等 要求 实现方法 求出以T为根结点的二叉树的深度并返回其值 1 先分别求得左 右子树的深度 3 求二叉树的深度 2 再将后根遍历算法中的 访问结点 的操作改为 求得左 右子树深度的最大值 最后将最大值加1后返回其值 从二叉树深度的定义可知 二叉树的深度应为其左 右子树深度的最大值加1 所以可利用后根遍历算法来实现 实现算法 书P168算法5 11 publicintgetDepth BiTreeNodeT if T null return0 intlDepth getDepth T getLchild intrDepth getDepth T getRchild return1 lDepth rDepth lDepth rDepth 3 求二叉树的深度 5 3 2二叉树的遍历应用举例 1 在二叉树上的查找某个结点 2 计算二叉树中结点的个数 3 求二叉树的深度 4 判断两棵二叉树是否相等 要求 实现方法 判断根结点为T1 T2的两棵二叉树是否相等 若相等 则返回true 否则 返回false 因为一棵二叉树由根 左子树和右子树三个部分组成 所以只有当两棵二叉树的三个组成部分都对应相等时 这两棵树才相等 而左 右子树的相等判断可以用对二叉树相等判断的同样方法来实现 即可用递归调用来实现 4 判断两棵二叉树是否相等 所以 可利用先根 中根 和后根遍历中的任何一种算法思想来实现 实现步骤 以中根遍历为例 1 若两棵二叉树都为空 则两棵二叉树相等 返回true 2 若两棵二叉树都非空 则 3 其它任何情况都返回false 若左子树相等 则继续判断它们的根结点是否相等 即转 若根结点的值相等 则继续判断它们的右子树是否相等 即转 若右子树也相等 则两棵二叉树相等 返回true 4 判断两棵二叉树是否相等 实现算法 书P168算法5 12 publicbooleanisEqual BiTreeNodeT1 BiTreeNodeT2 if T1 null if T1 null T2 null if isEqual T1 getLchild T2 getLchild if T1 getData equals T2 getData 4 判断两棵二叉树是否相等 if isEqual T1 getRchild T2 getRchild returntrue returnfalse 5 3 1二叉树的遍历方法及其实现 5 3 2二叉树遍历算法的应用举例 5 3 3建立二叉树 5 3二叉树的遍历 5 3 3建立二叉树 二叉链式存储结构 3 由标明空子树的先根遍历序列建二叉树 1 由先根和中根遍历序列建二叉树 2 由后根和中根遍历序列建二叉树 4 由完全二叉树的顺序存储结构建立二叉链式存储结构 1 由先根和中根遍历序列建二叉树 仅知二叉树的先序序列 abcdefg 不能唯一确定一棵二叉树 如果同时已知二叉树的中序序列 cbdaegf 则会如何 二叉树的先序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 1 由先根和中根遍历序列建二叉树 abcdefg cbdaegf 例如 a a b b c c d d e e f f g g a b c d e f g 先序序列中序序列 1 由先根和中根遍历序列建二叉树 算法 建立一棵二叉树的过程如下 其中 preOrder是整棵树的先根遍历序列 inOrder是整棵树的中根遍历序列 reIndex是先根遍历序列在preOrder中的开始位置 inIndex是中根遍历序列在inOrder中的开始位置 count表示树中结点的个数 1 由先根和中根遍历序列建二叉树 算法 实现方法 引入5个参数 preOrder inOrder preIndex inIndex和count 1 由先根和中根遍历序列建二叉树 算法 publicBiTree StringpreOrder StringinOrder intpreIndex intinIndex intcount if count 0 charr preOrder charAt preIndex for inti 0 i count i if r inOrder charAt i inIndex break root newBiTreeNode r root setLchild newBiTree preOrder inOrder preIndex 1 inIndex i root root setRchild newBiTree preOrder inOrder preIndex i 1 inIndex i 1 count i 1 root P170 算法5 13 5 3 3建立二叉树 二叉链式存储结构 3 由标明空子树的先根遍历序列建二叉树 1 由先根和中根遍历序列建二叉树 2 由后根和中根遍历序列建二叉树 4 由完全二叉树的顺序存储结构建立二叉链式存储结构 2 由后根和中根遍历序列建二叉树 二叉树的后序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 问 由二叉树的前序和后序序列是否也可以唯一确定一棵树 2 由后根和中根遍历序列建二叉树 由二叉树的前序和后序序列不可以唯一确定一棵树 如下二棵树 其前序遍历序列都为 AB 其后序遍历序列都为 BA 2 由后根和中根遍历序列建二叉树 算法 学生可依照算法5 13自行完成 略 5 3 3建立二叉树 二叉链式存储结构 3 由标明空子树的先根遍历序列建二叉树 1 由先根和中根遍历序列建二叉树 2 由后根和中根遍历序列建二叉树 4 由完全二叉树的顺序存储结构建立二叉链式存储结构 3 由标明空子树的先根遍历序列建二叉树 例如 以字符 表示 AB C D 空树 只含一个根结点 A 以下列字符串表示 标明空子树的先根遍历序列就是在先根遍历序列中加入空树信息 以字符串 A 表示 3 由标明空子树的先根遍历序列建二叉树 算法步骤 在完整先根遍历数据输入正确的前提下 由此建立二叉链表的算法为 若读入的字符是 则建立空树 否则建立根结点 递归建立左子树的二叉链表 递归建立右子树的二叉链表 3 由标明空子树的先根遍历序列建二叉树 publicBiTree StringpreStr 算法5 14结束 P172 算法5 14 privateintindex 0 用于记从preStr中取字符的位置 charc preStr charAt index if c else root newBiTreeNode c 建立树的根结点 root setLchild newBiTree preStr root 建立树的左子树 root setRchild newBiTree preStr root 建立树的右子树 root null 5 3 3建立二叉树 二叉链式存储结构 3 由标明空子树的先根遍历序列建二叉树 1 由先根和中根遍历序列建二叉树 2 由后根和中根遍历序列建二叉树 4 由完全二叉树的顺序存储结构建立二叉链式存储结构 4 由完全二叉树的顺序存储结构建立二叉链式存储结构 完全二叉树 其对应的顺序存储结构 右孩子的编号为 由二叉树的性质5可知 结点编号规则 根结点的编号为 0 编号为i的结点其左孩子的编号为 2i 1 2i 2 4 由完全二叉树的顺序存储结构建立二叉链式存储结构 publicBiTreeNodecreateBiTree StringsqBiTree intindex P173 Exam5 7中 BiTreeNoderoot null if index sqBitree length root newBiTreeNode sqBiTree charAt index root setLchild creatBiTree sqBiTree 2 i 1 建立树的左子树 root setRchild creatBiTree sqBiTree 2 i 2 建立树的右子树 returnroot 算法 作业1 习题五中的三 1 2 附加题如下 1 已知一棵度为m的树中有n1个度为1的结点 n2个度为2的结点 nm个度为m的结点 问该树中有多少片叶子 2 试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构 附加题 附加题 3 分别写出题2中二叉树的先根 中根和后序根遍历序列 4 已知一棵树二叉树的后根遍历和中根遍历的序列分别为 ACDBGIHFE和ABCDEFGHI 请画出该二叉树 并写出它的先根遍历的序列 5 已知一棵树二叉树的先根遍历和中根遍历的序列分别为 ABDGHCEFI和GDHBAECIF 请画出此二叉树 并写出它的后根遍的序列 1 已知一棵度为m的树中有n1个度为1的结点 n2个度结点 nm个度为m的结点 问该树中有多少片叶子 解 设树的总结点个数为n 叶子结点的个数为n0 则n n0 n1 n2 nm 1 又因为树的总分支数为n 1 且n 1 n1 n2 2 n3 3 nm m 2 1 2 得1 n0 n1 2n2 m 1 nm则 n0 1 n2 2n3 m 1 nm 附加题解答 2 试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构 二叉链式存储结构 顺序存储结构 附加题解答 3 分别写出题2中二叉树的先根 中根和后序根遍历序列 前根序列 ABDEGCFH 中根序列 DBGEACHF 后根序列 DGEBHFCA 附加题解答 4 已知一棵树二叉树的后根遍历和中根遍历的序列分别为 ACDBGIHFE和ABCDEFGHI 请画出该二叉树 并写出它的先根遍历的序列 先根遍历序列 EBADCFHGI 构造的二叉树如下 附加题解答 5 已知一棵树二叉树的先根遍历和中根遍历的序列分别为 ABDGHCEFI和GDHBAECIF 请画出此二叉树 并写出它的后根遍的序列 后根遍历序列 GHDBEIFCA 构造的二叉树如下 附加题解答 5 4 1哈夫曼树的基本概念 5 4 2哈夫曼树和哈夫曼编码的构造方法 5 4 3构造哈夫曼树和哈夫曼编码类的描述 5 4哈夫曼树及哈夫曼编码 5 4 1哈夫曼树的基本概念 结点的路径长度 结点间的路径 从一个结点到另一个结点所经历的结点和分支序列 从根结点到该结点的路径上分支的数目 结点的权 在实际应用中 人们往住会给树中的每一个结点赋予一个具有某种实际意义的数值 这个数值被称为该结点的权值 5 4 1哈夫曼树的基本概念 树的带权路径长度 结点的带权路径长度 结点的路径长度与该结点的权值的乘积 树中所有叶结点的带权路径长度之和 假设树上有n个叶结点 通常记作 其中Li为带权wi的叶子结点的带权路径长度 5 4 1哈夫曼树的基本概念 最优二叉树 给定n个权值并作为n个叶结点按一定规则构造一棵二叉树 使其带权路径长度达到最小值 则这棵二叉树被称为最优二叉树 也称哈夫曼树 在所有含n个叶子结点 并带相同权值的二叉树中 必存在一棵其带权路径长度取最小值的树 这树就是 最优树 WPL T 7 2 5 2 2 3 4 3 9 2 60 WPL T 7 4 9 4 5 3 4 2 2 1 89 5 4 1哈夫曼树的基本概念 如何构造最优树 哈夫曼树 呢 5 4 1哈夫曼树的基本概念 5 4 2哈夫曼树和哈夫曼编码的构造方法 5 4 3构造哈夫曼树和哈夫曼编码类的描述 5 4哈夫曼树及哈夫曼编码 5 4 2哈夫曼树及哈夫曼编码的构造方法 1 根据给定的n个权值 w1 w2 wn 构造一个由n棵二叉树所构成的集合F T1 T2 Tn 其中每棵二叉树中均只含一个带权值为wi的根结点 其左 右子树为空树 赫夫曼算法的主要步骤 P175 5 4 2哈夫曼树及哈夫曼编码的构造 赫夫曼算法的主要步骤 P175 2 在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树 分别把它们作为左子树和右子树去构造一棵新二叉树 新二叉树的根结点权值为其左 右子树根结点的权值之和 5 4 2哈夫曼树及哈夫曼编码的构造方法 赫夫曼算法的主要步骤 P175 3 作为新二叉树的左 右子树的这两棵二叉树从森林F中删除 同时加入刚生成的新二叉树 4 重复 2 和 3 两步 直至F中只含一棵二叉树为止 则这种棵二叉树就是所构成的哈夫曼树 5 4 2哈夫曼树及哈夫曼编码的构造方法 9 例如 已知权值W 5 6 2 9 7 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 5 4 2哈夫曼树及哈夫曼编码的构造方法 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 哈夫曼码 9 5 2 7 16 5 4 2哈夫曼树及哈夫曼编码的构造方法 再例如 书P177的 例5 8 由学生完成 已知在一个信息通信联络中使用了8个字符 a b c d e f g和h 每个字符的使用频度分别为 6 30 8 9 15 24 4和12 试设计各个字符的哈夫曼编码 问 一棵有n个叶子结点的哈夫曼树共有多少个结点 2 n 1个 5 4 2哈夫曼树及哈夫曼编码的构造方法 用哈夫曼树进行译码 指的是 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 前缀编码 哈夫曼编码是一种前缀码 从哈夫曼树的根开始 从左到右把二进制编码的每一位进行判别 若遇到0 则选择左分支走向下一个结点 若遇到1 则选择右分支走向下一个结点 直至到达一个树叶结点 便求得相应字符 译码过程是编码过程的逆过程 5 4 1哈夫曼树的基本概念 5 4 2哈夫曼树和哈夫曼编码的构造方法 5 4 3构造哈夫曼树和哈夫曼编码类的描述 5 4哈夫曼树及哈夫曼编码 5 4 3哈夫曼树及哈夫曼编码类的描述 哈夫曼树的结点存储结构示意图 其中 weight域存放结点的权值 flag域存放结点是否加入哈夫曼树的标志值 等于1时表示已加入 否则没加入 parent rchild lchild域分别存放父结点 左 右孩子结点的地址 5 4 3哈夫曼树及哈夫曼编码类的描述 哈夫曼树的结点类描述 书中P178 publicclassHuffmanNode publicHuffmanNode 构造一个空结点this null 构造一个左 右孩子域为空的结点publicHuffmanNode intweight this weight weight flag 0 parent lchild rchild null privateintweight 结点的数据域privateintflag 结点是否加入哈夫曼树的标志privateHuffmanNodeparent lchild rchild 父结点 左 右孩子结点域 5 4 3哈夫曼树及哈夫曼编码类的描述 构造哈夫曼树和哈夫曼编码的类描述 publicclassHuffmanTree 略 书中P179 publicint huffmanCoding int W intn W length 字符个数intm 2 n 1 哈夫曼树的结点数 5 4 3哈夫曼树及哈夫曼编码类的描述 例如 对于书P177例5 8 按HuffmanTree类中的HuffmanCoding方法可构造如下图的一棵二棵树 weightflagparentlchildrchild 01234567891011121314 其存储结构HN的初始和终结状态分别如下图所示 weightflagparentlchildrchild 01234567891011121314 5 4 3哈夫曼树及哈夫曼编码类的描述 所得的哈夫曼编码如下图所示 5 5 1树 森林与二叉树之间的转换 5 5 2树的存储结构 5 5 3树与森林的遍历 5 5树与森林 5 5 1树 森林与二叉树之间的转换 1 树转换成二叉树的规则 左孩子右兄弟 5 5 1树 森林与二叉树之间的转换 树转换成二叉树可形象描述为以下3个步骤 1 加线 2 删线 3 旋转 树 二叉树 5 5 1树 森林与二叉树之间的转换 2 二叉树转换成树的规则 是树转换成二叉树的逆过程 1 加线 2 删线 3 旋转 二叉树 树 5 5 1树 森林与二叉树之间的转换 3 森林转换成二叉树的规则 若F 则B 否则 由ROOT T1 对应得到Node root 由 t11 t12 t1m 对应得到LBT 由 T2 T3 Tn 对应得到RBT 树与二叉树的对应 例如 如下森林转化成二叉树的过程为 5 5 1树 森林与二叉树之间的转换 树根相连 将森林中后一棵树视为前一棵树的右子树 5 5 1树 森林与二叉树之间的转换 4 二叉树转换为森林的规则为 若B 则F 否则 由Node root 对应得到ROOT T1 由LBT对应得到 t11 t12 t1m 由RBT对应得到 T2 T3 Tn 转换过程是森林转换成二叉树的逆过程 5 5 1树 森林与二叉树之间的转换 5 5 1树 森林与二叉树之间的转换 5 5 2树的存储结构 5 5 3树与森林的遍历 5 5树与森林 5 5 2树的存储结构 1 双亲链表存储结构 2 孩子链表存储结构 4 孩子兄弟链表存储结构 重点掌握 树的四种存储结构 3 双亲孩子链表存储结构 5 5 2树的存储结构 1 双亲链表存储结构 5 5 2树的存储结构 2 孩子链表存储结构 5 5 2树的存储结构 3 双亲孩子链表存储结构 5 5 2树的存储结构 4 孩子兄弟链表存储结构 左孩子右兄弟 5 5 2树的存储结构 4 孩子兄弟链表存储结构 孩子兄弟链表中结点类的描述 publicclassCSTreeNode privateObjectdata 结点的数据域privateCSTreeNodefirstchild nextsiblin