数据结构第六章树和二叉树ppt课件.ppt

数据结构 第6章树和二叉树 线性结构 线性表 顺序表 链表 栈和队列数组 广义表非线性结构 树图 引言 主要内容 6 1树及其抽象数据类型6 2二叉树6 3线索二叉树6 4Huffman树6 5树的表示和实现 树结构是一类重要的非线性结构 树结构是结点之间有分支 并且具有层次关系的结构 它非常类似于自然界中的树 树结构在客观世界中是大量存在的 例如家谱 行政组织机构都可用树形象地表示 树在计算机领域中也有着广泛的应用 例如在编译程序中 用树来表示源程序的语法结构 在数据库系统中 可用树来组织信息 在分析算法的行为时 可用树来描述其执行过程 等等 6 1树及其抽象数据类型 树结构 6 1树及其抽象数据类型 树结构举例 由上可知 在树结构中 除根结点以外的结点只有一个直接前驱结点 可以有零个至多个直接后继结点 根结点没有前驱结点 6 1树及其抽象数据类型 树结构 树 Tree 是由n n 0 个结点组成的有限集合 n 0的树称为空树 n 0的树由以下两个条件约定构成 1 有且仅有一个特殊的称为根 Root 的结点 它只有后继结点 没有前驱结点 2 其余的结点可分为m n m 0 个互不相交的子集T0 T1 T2 Tm 1 其中每个子集又是一棵树 并称其为子树 Subtree 6 1树及其抽象数据类型 树定义 比如上图 左边为只有一个结点的树 A为根 右边是一个有8个结点的树 A为根 其余可以分为三个不相交的子集 也就是可以分为三个子树 A 6 1树及其抽象数据类型 树定义 6 1树及其抽象数据类型 树定义 结点的双亲结点或父母结点 parent 结点上面的相邻结点 或指结点的前驱结点结点n的孩子结点 child 任何一个以n作为双亲结点的结点 或指结点n的后继结点树的根 root 有且仅有的一个特定的结点 它没有双亲结点 6 1树及其抽象数据类型 基本术语 结点n的祖先结点 ancestor 包括n的双亲结点 n的双亲结点的双亲结点 等等 即指从根结点到其父母结点所经过的所有结点根是树中所有结点的公共祖先结点结点n的子孙 后代 结点 descendant 任何一个以n作为祖先结点的结点 即指结点的所有孩子结点 以及孩子的孩子等兄弟结点 sibling 如果结点m和n共有一个双亲结点 则称m和n为兄弟结点 6 1树及其抽象数据类型 基本术语 叶子结点 终端结点 leaf 没有孩子结点的结点分支结点 非终端结点 叶子结点之外的结点称为分支结点或者非终端结点子树 subtree 在树T中 n的子孙结点组成了以n作为根的T的子树 6 1树及其抽象数据类型 基本术语 结点n的度 degreeofnode n的孩子结点的数量树的度 degreeofatree 树中所有结点的最大度数 6 1树及其抽象数据类型 基本术语 结点n的层次 level 结点n所处的树中的层次位置 可以假设根的层次是0或1 本书中所有都假设根的层次为1 其他结点的层次是其父母结点的层次加1树的高度 heigh 或深度 depth 树中结点的最大层次数 6 1树及其抽象数据类型 基本术语 边 edge 设树中X结点是Y结点的父母结点 有序对 X Y 称为连接这两个结点的分支 也称为边路径 path 从一个结点n到另一个结点的边序列 如设 X0 X1 Xk 1 是由树中结点组成的一个序列 且 Xi Xi 1 都是树中的边 则该序列称为X0到Xk 1的一条路径路径长度 length 路径中涉及到边的数量 6 1树及其抽象数据类型 基本术语 若把树中每个结点的各子树看成从左到右有次序的 即不能互换 则称该树为有序树 OrderedTree 否则称为无序树 UnorderedTree 森林 forest m棵互不相交的树的集合 如 T0 T1 T2 Tm 1 但可能为空 6 1树及其抽象数据类型 基本术语 1 树形结构表示法 图示法 具体参见下图 6 1树及其抽象数据类型 树的表示 2 横向凹入表示法具体参见下图 6 1树及其抽象数据类型 树的表示 3 嵌套集合表示法 文氏图表示法 具体参见下图 6 1树及其抽象数据类型 树的表示 4 广义表表示法对图6 1 c 的树结构 广义表表示法可表示为 A B E J K L F C G D H M I 6 1树及其抽象数据类型 树的表示 ADTTree 树抽象数据类型 booleanisEmpty 判空intlevel Tkey 层次intsize 结点数intheight 高度voidpreorder 先根次序遍历voidpostorder 后根次序遍历voidlevelorder 层次遍历TreeNodeinsert Tx 插入元素x作为根TreeNodeinsert TreeNodep Tx inti 插入x作为p结点的第i 0 个孩子voidremove TreeNodep inti 删除子树voidclear 删除所有结点TreeNodesearch Tkey 查找booleancontains Tkey 包含Tremove Tkey 删除子树 6 1树及其抽象数据类型 树的抽象数据类型 6 2二叉树 二叉树定义1 树的度小于等于2的树 不完善 二叉树定义2 二叉树是一特殊的树结构 它的特点是每个结点最多只能有两个子树 即在树中不存在度大于2的结点 左孩子结点 leftchild 二叉树中结点的左孩子右孩子结点 rightchild 二叉树中结点的右孩子二叉树定义3 二叉树是n个结点的有限集合 空二叉树 由一个根结点 两棵互不相交的左子树和右子树组成 二叉树的定义 6 2二叉树 二叉树的定义 图二叉树的5种基本形态 二叉树结点的子树要区分左子树和右子树 即使只有一棵子树也要进行区分 说明它是左子树 还是右子树 这是二叉树与树的最主要的差别 下图列出二差树的5种基本形态 图 c 和图 d 是不同的两棵二叉树 思考题6 1 二叉树与树的差别 二叉树是不是度为2的树 二叉树是不是度为2的有序树 为什么 2个结点的树和二叉树的基本形态 6 2二叉树 二叉树的定义 思考题6 1 画出3个结点的树和二叉树的基本形态 6 2二叉树 二叉树的定义 6 2二叉树 二叉树的性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 用归纳法证明 归纳基 归纳假设 归纳证明 i 1层时 只有一个根结点 2i 1 20 1 假设对所有的j 1 j i 命题成立 即第j层上至多有2j 1个结点 因二叉树上每个结点至多有两棵子树 则第i层的结点数 2 i 1 1 2 2i 1 证明j i时命题成立 第i 1层的结点数 8 6 2二叉树 二叉树的性质 性质2 深度为k的二叉树上至多含2k 1个结点 k 1 证明 基于上一条性质 深度为k的二叉树上的结点数至多为20 21 2k 1 1 1 2k 1 2 2k 1 性质3 对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的结点 则必存在关系式 n0 n2 1 证明 设二叉树上结点总数n n0 n1 n2 又设二叉树上分支总数为b 则 从前驱 入支 角度 从下向上 有b n 1 从后继 出支 角度 从上向下 有b n1 2n2 0 n0 从而有 n0 n1 n2 1 n1 2n2由此 n0 n2 1 6 2二叉树 二叉树的性质 满二叉树 fullbinarytree 一棵高度为h且有2h 1 h 0 个结点的二叉树称为满二叉树 以下说法是否正确 二叉树中所有非叶结点的度数都为2的二叉树是满二叉树 错 一个高度为h的满二叉树中 只在h层有叶结点 而且每一个非叶子结点都是满的 是满二叉树 对 6 2二叉树 二叉树的性质 完全二叉树 completebinarytree 如果深度为h 由n个结点的二叉树中每个结点能够与深度为h的顺序编号的满二叉树从0到n 1标号的结点一一对应 则称这样的二叉树为完全二叉树 满二叉树是完全二叉树的特例 完全二叉树的特点是 在h层二叉树中 所有的叶结点都出现在第h层或h 1层 对任一结点 如果其右子树的最大层次为h 则其左子树的最大层次为h或h 1 6 2二叉树 二叉树的性质 6 2二叉树 二叉树的性质 6 2二叉树 二叉树的性质 性质4 具有n个结点的完全二叉树的深度为 log2n 1 证明 设完全二叉树的深度为k则根据第二条性质得2k 1 1 n 2k 1或2k 1 n 2k两边取对数得 k 1 log2n kk log2n 1 k 1因为k只能是整数 因此 k log2n 1 深度为k的二叉树上至多含2k 1个结点 k 1 特点 6 2二叉树 二叉树的性质 性质5 一棵具有n个结点的完全二叉树 对序号为i 0 i n 的结点 有 若i 0 则i为根结点 无父母结点 若i 0 则i的父母结点序号为 i 1 2 若2i 1 n 则i的左孩子结点在2i 1 否则i无左孩子 若2i 2 n 则i的右孩子结点在2i 2 否则i无右孩子 6 2二叉树 二叉树的遍历规则 线形表的遍历过程 从首元素开始 访问 某个操作 每一个元素 直到尾元素 树性结构如何遍历 回顾线形数据结构的遍历 6 2二叉树 二叉树的遍历规则 二叉树的遍历指的是沿某条搜索路径访问二叉树 对二叉树中的每个结点访问一次且仅一次 这里的 访问 实际上指的是对结点进行某种操作 以下 访问 特指打印该结点信息 定义 所有遍历序列有6种 ABC BAC BCA 先左孩子CBA CAB ACB 先右孩子约定遍历子树的次序是先左子树后右子树 6 2二叉树 二叉树的遍历规则 孩子优先的遍历规则 先根次序 访问根结点 先根遍历左子树 先根遍历右子树 中根次序 中根遍历左子树 访问根结点 中根遍历右子树 后根次序 后根遍历左子树 后根遍历右子树 访问根结点 先根遍历序列 ABDGCEFH中根遍历序列 DGBAECHF后根遍历序列 GDBEHFCA 孩子优先的遍历规则 6 2二叉树 二叉树的遍历规则 层次遍历序列 ABCDEFGH 兄弟优先的遍历规则 6 2二叉树 二叉树的遍历规则 给出二叉树的先根 中根 后根和层次遍历序列 习题 6 2二叉树 二叉树的遍历规则 ADTBinaryTree booleanisEmpty 判空intsize 结点数intheight 高度voidpreOrder 先根次序遍历voidinOrder 中根次序遍历voidpostOrder 后根次序遍历voidlevelOrder 按层次遍历BinaryNodeinsert Tx 插入根BinaryNodeinsert BinaryNodep Tx booleanleftChild 插入孩子voidremove BinaryNodeparent booleanleftChild 删除子树voidclear 删除所有结点BinaryNodesearch Tkey 查找booleancontains Tkey 包含intlevel Tkey key结点所在层次 6 2二叉树 二叉树抽象数据类型 顺序存储结构链式存储结构 6 2二叉树 二叉树的存储结构 二叉树的顺序存储结构 顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素顺序存储结构的特点 存储单元仅仅存储结点的值二叉树结点之间的逻辑关系由数组中下标的顺序来体现 6 2二叉树 二叉树的存储结构 因此 必须把二叉树的所有结点安排成为一个恰当的序列 结点在这个序列中的相互位置能反映出结点之间的逻辑关系 首先要为一个深度为h的树分配一个大小为2h 1的数组然后用此数组自上而下 自左而右地存储与此树对应的完全二叉树上的结点 二叉树的顺序存储结构 6 2二叉树 二叉树的存储结构 二叉树顺序存储的原则 不管给定的二叉树是不是完全二叉树 都看作完全二叉树 即按完全二叉树的层次次序 从上到下 从左到右 把各结点依次存入数组中此结构有什么缺点 二叉树的顺序存储结构 6 2二叉树 二叉树的存储结构 二叉树的顺序存储结构 6 2二叉树 二叉树的存储结构 二叉树的顺序存储结构 6 2二叉树 二叉树的存储结构 二叉树顺序存储结构中其他结点的确定 性质5 假设给定结点的地址为I 则 1 若I 0 则该结点是为根结点 无父亲 2 若I 0 则该结点的父亲结点地址为I 1 2的整数部分 3 若2 I 1 n 则该结点的左儿子结点地址为2 I 1 否则该结点无左儿子 4 若2 I 2 n 则该结点的右儿子结点地址为2 I 2 否则该结点无右儿子 5 若I为奇数 除根结点 则该结点的右兄弟为I 1 6 若I为偶数 除根结点 则该结点的左兄弟为I 1 二叉树的顺序存储结构 6 2二叉树 二叉树的存储结构 对于一棵二叉树 若采用顺序存贮时 当它为完全二叉树时 比较方便 若为非完全二叉树 将会浪费大量存贮存贮单元 最坏的非完全二叉树是全部只有右分支 设高度为K 则需占用2K 1个存贮单元 而实际只有k个元素 实际只需k个存储单元 因此 对于非完全二叉树 宜采用下面的链式存储结构 二叉树的顺序存储结构 6 2二叉树 二叉树的存储结构 由二叉树的定义可知 二叉树的结点由一个数据元素和两个分别指向其左右子树的两个分支构成 所以二叉树的结点包括两个部分 数据域 左 右指针域 有时候为了方便找到该结点的双亲还会在设置一个指针域指向其双亲结点 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 二叉链表中一个结点可描述为 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 如何采用以上结点结构表示二叉树 采用链式存储结构表示二叉树时 需要一个根指针 root 指向根结点若二叉树为空 则根结点为NULL若结点的某个儿子不存在 则相应的指针为空 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 对于上图所示二叉树 用二叉链表形式描述见下图 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 考虑 n个结点的二叉树中 有多少个指针域 其中多少个指向左 右孩子 多少个为空 若一棵二叉树有n个结点 采用二叉链表作存贮结构时 共有2n个指针域 其中只有n 1个指针指向左右孩子 其余n 1个指针为空 没有发挥作用 被白白浪费掉了 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 在二叉链表结点的基础上 三叉链表增加一条链parent连接父母结点 这样就存储了父母结点与孩子结点的双向关系 每个结点至少有4个域 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 二叉树的链式存储结构 6 2二叉树 二叉树的存储结构 二叉树的二叉链表结点类publicclassBinaryNode Tdata 数据元素BinaryNodeleft right 左 右孩子publicBinaryNode Tdata BinaryNodeleft BinaryNoderight 构造结点publicBinaryNode Tdata 构造叶子publicStringtoString 描述字符串publicbooleanisLeaf 判结点 6 2二叉树 二叉树的二叉链表实现 1 二叉链表结点类publicclassBinaryNode 二叉树的二叉链表结点类 T指定结点的元素类型 publicTdata 数据域 存储数据元素publicBinaryNodeleft right 链域 分别指向左 右孩子结点 构造结点 data指定元素 left right分别指向左孩子和右孩子结点publicBinaryNode Tdata BinaryNodeleft BinaryNoderight this data data this left left this right right 6 2二叉树 二叉树的二叉链表实现 二叉树的结点类publicBinaryNode Tdata 构造元素为data的叶子结点 this data null null publicStringtoString 返回结点数据域的描述字符串 returnthis data toString publicbooleanisLeaf 判断是否叶子结点 returnthis left null 6 2二叉树 二叉树的二叉链表实现 二叉树类publicclassBinaryTree BinaryNoderoot 根结点publicBinaryTree 构造空树publicbooleanisEmpty 判空 6 2二叉树 二叉树的二叉链表实现 二叉树类publicclassBinaryTree 二叉树类 二叉链表存储 T指定结点的元素类型 publicBinaryNoderoot 根结点 二叉链表结点结构publicBinaryTree 构造空二叉树 this root null publicbooleanisEmpty 判断是否空二叉树 returnthis root null 6 2二叉树 二叉树的二叉链表实现 二叉树插入结点 BinaryNodeinsert Tx 插入根结点BinaryNodeinsert BinaryNodeparent Tx booleanleftChild 插入x为parent结点的左 右孩子 6 2二叉树 二叉树的二叉链表实现 publicBinaryNodeinsert Tx 插入x作为根结点 原根结点作为x的左孩子 返回插入结点 returnthis root newBinaryNode x this root null 插入x为parent结点的左 右孩子 leftChild指定孩子 取值为true 左 false 右 parent的原左 右孩子成为x结点的左 右孩子 返回插入结点 若x null 不插入 返回null 若parent null Java抛出空对象异常 publicBinaryNodeinsert BinaryNodeparent Tx booleanleftChild if x null returnnull if leftChild 插入x为parent结点的左 右孩子 返回插入结点returnparent left newBinaryNode x parent left null returnparent right newBinaryNode x null parent right 6 2二叉树 二叉树的二叉链表实现 删除parent结点的左 右子树publicvoidremove BinaryNodeparent booleanleftChild publicvoidclear 删除所有结点 6 2二叉树 二叉树的二叉链表实现 二叉树删除子树 删除parent结点的左或右子树 leftChild指定子树 取值为true 左 false 右 Java自动收回被删除子树占用的存储空间 publicvoidremove BinaryNodeparent booleanleftChild if leftChild parent left null 若parent null Java抛出空对象异常elseparent right null publicvoidclear 删除二叉树的所有结点 this root null 6 2二叉树 二叉树的二叉链表实现 先根遍历 1 按先根次序遍历二叉树的递归算法 将如下算法添加到二叉树类BinaryTree中若二叉树为空 返回 否则 继续 从根结点开始 访问当前结点 按先根次序遍历当前结点的左子树 按先根次序遍历当前结点的右子树 privatevoidpreorder BinaryNodep 先根次序遍历以p结点为根的子树 递归方法 if p null 若二叉树不空 System out print p data toString 先访问当前结点元素preorder p left 按先根次序遍历p的左子树 递归调用 参数为左孩子preorder p right 按先根次序遍历p的右子树 递归调用 参数为右孩子 6 2二叉树 二叉树的二叉链表实现 递归方法必须有参数 通过不同的实际参数区别递归调用执行中的多个方法 一棵二叉树由多棵子树组成 一个结点也是一棵子树的根 二叉树类中实现遍历规则的递归算法以p为参数 表示以某种次序遍历以p结点为根的子树 当p指向不同结点时 遍历不同的子树 当p为空子树时 递归结束 二叉树类还必须提供从根结点开始遍历的方法 因此 每种遍历算法由两个重载方法实现 如preOrder 和preOrder p 先根遍历 二叉树的二叉链表实现 6 2二叉树 publicvoidpreorder 输出先根次序遍历序列 System out print 先根次序遍历二叉树 preorder this root 调用先根次序遍历二叉树的递归方法System out println 先根遍历 二叉树的二叉链表实现 6 2二叉树 publicStringtoString 返回先根次序遍历二叉树所有结点的描述字符串 returntoString this root privateStringtoString BinaryNodep 返回先根次序遍历以p为根的子树描述字符串 递归方法 if p null return 输出空子树标记returnp data toString toString p left toString p right 先根遍历 二叉树的二叉链表实现 6 2二叉树 将如下算法添加到二叉树类BinaryTree中publicvoidinorder 输出中根次序遍历序列 System out print 中根次序遍历二叉树 inorder this root System out println privatevoidinorder BinaryNodep 中根次序遍历以p结点为根的子树 递归方法 if p null inorder p left 中根次序遍历p的左子树 递归调用System out print p data toString inorder p right 中根次序遍历p的右子树 递归调用 中根遍历 二叉树的二叉链表实现 6 2二叉树 将如下算法添加到二叉树类BinaryTree中publicvoidpostorder 输出后根次序遍历序列 System out print 后根次序遍历二叉树 postorder this root System out println privatevoidpostorder BinaryNodep 后根次序遍历以p结点为根的子树 递归方法 if p null postorder p left postorder p right System out print p data toString 后访问当前结点元素 后根遍历 二叉树的二叉链表实现 6 2二叉树 仅知二叉树的先序序列 abcdefg 不能唯一确定一棵二叉树 如果同时已知二叉树的中序序列 cbdaegf 则会如何 思考题由二叉树的先序和中序序列建树 二叉树的先序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 确定原则 由先序序列确定二叉树的根结点 由中序序列确定二叉树的左右子树序列 二叉树的二叉链表实现 6 2二叉树 abcdefg cbdaegf a a b b c c d d e e f f g g a b c d e f g 先序序列中序序列 由二叉树的先序和中序序序列确定二叉树 二叉树的二叉链表实现 6 2二叉树 已知一个二叉树的先根遍历序列和中根遍历序列 能否画出这个二叉树 可以 已知一个二叉树的后根遍历序列和中根遍历序列 能否画出这个二叉树 可以 已知一个二叉树的先根遍历序列和后根遍历序列 能否画出这个二叉树 不可以 二叉树的二叉链表实现 6 2二叉树 思考题 基于遍历的操作 求结点个数求高度查找获得父母结点 二叉树的二叉链表实现 6 2二叉树 求结点个数publicintsize 返回二叉树的结点数 returnsize root publicintsize BinaryNodep 返回以p结点为根的子树的结点数 if p null return0 return1 size p left size p right 基于遍历的操作 二叉树的二叉链表实现 6 2二叉树 求高度 必须采用后跟次序遍历算法 只有先分别计算出左 右子树高度的情况下 才能计算当前子树高度publicintheight 返回二叉树的高度 returnheight root publicintheight BinaryNodep 返回以p结点为根的子树高度 后根次序遍历 if p null return0 intlh height p left 返回左子树的高度intrh height p right 返回右子树的高度return lh rh lh 1 rh 1 当前子树高度为较高子树的高度加1 基于遍历的操作 二叉树的二叉链表实现 6 2二叉树 查找publicTsearch Tkey 查找并返回首次出现的关键字为key元素 returnsearchNode root key data publicBinaryNodesearchNode Tkey 查找并返回首次出现的关键字为key元素结点 returnsearchNode root key 在以p为根的子树中查找并返回首次出现的关键字为key元素结点 若未找到返回null 先根次序遍历publicBinaryNodesearchNode BinaryNodep Tkey if p null key null returnnull if p data equals key returnp 查找成功 返回找到结点BinaryNodefind searchNode p left key 在左子树中查找 递归调用if find null 若在左子树中未找到find searchNode p right key 则继续在右子树中查找 递归调用returnfind 返回查找结果 基于遍历的操作 二叉树的二叉链表实现 6 2二叉树 获得父母结点 返回node结点的父母结点 若空树 未找到或node为根 则返回nullpublicBinaryNodegetParent BinaryNodenode if root null node null node root returnnull returngetParent root node 在以p为根的子树中查找并返回node结点的父母结点publicBinaryNodegetParent BinaryNodep BinaryNodenode if p null returnnull if p left node p right node returnp BinaryNodefind getParent p left node if find null find getParent p right node returnfind 基于遍历的操作 二叉树的二叉链表实现 6 2二叉树 返回以p结点为根子树的结点数intsize BinaryNodep staticintn 0 if p null n size p left size p right 习题解答 存在错误 Java语言方法体中的局部变量不能声明为static 如果用局部变量n计数 每次n 0 再n n 1 无法实现计数 并且结果无法返回给调用者 思考题递归方法参数与返回值问题讨论 有什么错误 二叉树的二叉链表实现 6 2二叉树 构造二叉树 构造一棵二叉树必须明确以下两种关系 结点与其双亲结点及孩子结点间的层次关系 兄弟结点间左或右的次序关系 关系的确定 先根遍历和后跟遍历反映双亲与孩子结点之间的层次关系中跟遍历反映兄弟结点之间的左右关系总之 由二叉树的一种遍历序列不能唯一确定一颗二叉树 二叉树的二叉链表实现 6 2二叉树 由二叉树的一种遍历序列不能唯一确定一棵二叉树先根遍历序列为AB 构造二叉树 二叉树的二叉链表实现 6 2二叉树 书上介绍的建立二叉树的方法 按先根和中根次序遍历序列建立二叉树以标明空子树的先根次序遍历序列建立二叉树以广义表表示建立二叉树建立链式存储结构的完全二叉树 构造二叉树 二叉树的二叉链表实现 6 2二叉树 按先根和中根遍历序列建立二叉树 在二叉树类BinaryTree中 增加create 方法实现以先根遍历序列prelist 中根遍历序列inlist建立一颗二叉树的算法 并返回这颗二叉树的根结点具体的实现思想就是书上 P148 的证明过程 二叉树的二叉链表实现 6 2二叉树 先根和中根序列表示 按先根和中根遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 publicBinaryTree T prelist T inlist 以先根和中根序列构造二叉树 this root create prelist inlist 0 0 prelist length 按先根和中根遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 以先根和中根序列创建一棵子树 子树根结点值是 prelist preStart n指定子序列长度 返回所创建子树的根结点privateBinaryNodecreate T prelist T inlist intpreStart intinStart intn System out print prelist print prelist preStart n System out print inlist print inlist inStart n System out println if n 0 returnnull 按先根和中根遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 Telem prelist preStart 根结点值BinaryNodep newBinaryNode elem 创建叶子结点inti 0 while i n 按先根和中根遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 privatevoidprint T table intstart intn for inti 0 i n i System out print table start i 按先根和中根遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 publicstaticvoidmain Stringargs String prelist A B D G C E F H String inlist D G B A E C H F BinaryTreebitree newBinaryTree prelist inlist bitree preOrder bitree inOrder bitree postOrder 按先根和中根遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 中根遍历序列 CBDFEGAMLNKJOPRQIHS后根遍历序列 CFGEDBMNLKRQPOJISHA 思考题由中根和后根遍历序列构造二叉树 二叉树的二叉链表实现 6 2二叉树 习题解答 二叉树的二叉链表实现 6 2二叉树 以标明空子树的先根次序遍历序列建立二叉树 仅有先根遍历不能唯一确定一颗二叉树 但是 如果在先根遍历中加入反映兄弟结点间的左右次序的信息 如以 标明空子树 则可以唯一确定一颗二叉树 二叉树的二叉链表实现 6 2二叉树 以标明空子树的先根次序遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 构造过程 设prelist表示一棵二叉树标明空子树的先根序列 构造算法如下 prelist 0 一定是二叉树的根 创建根结点 prelist 1 一定是根的左孩子 若prelist i 不是 则创建一个结点 该结点的左孩子结点元素是prelist i 1 但父母与孩子结点之间的链还未建立 否则当前子树为空 返回上一层结点 返回到当前结点时 下一个元素prelist i 1 是当前结点的右孩子结点 当一个结点的左右孩子链都已建立 则以当前结点为根的一棵子树就已建立 返回上一层结点 重复执行步骤2 3 直到返回根结点 则二叉树建立 使root指向根结点 以标明空子树的先根次序遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 在BinaryTree类中增加以下构造方法 以标明空子树的先根序列建立一棵二叉树publicBinaryTree T prelist 以标明空子树的先根序列构造二叉树 this root create prelist privateinti 0 privateBinaryNodecreate T prelist 从i开始 创建一棵以prelist i 为根的子树 返回根结点 递归方法 以标明空子树的先根次序遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 以从i开始的标明空子树的先根序列 创建一棵以prelist i 为根的子树 返回根结点 递归方法privateinti 0 privateBinaryNodecreate T prelist BinaryNodep null if i elem 创建叶子结点p left create prelist 创建p的左子树 递归调用 实际参数与形式参数相同p right create prelist 创建p的右子树 递归调用 实际参数与形式参数相同 returnp 以标明空子树的先根次序遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 String preorder2 A B null null C 标明空子树的先根序列BinaryTreebitree3 newBinaryTree preorder2 bitree3 preOrder bitree3 inOrder bitree3 postOrder 以标明空子树的先根次序遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 思考题二叉树的构造 遍历及插入 以标明空子树的先根次序遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 思考题能否采用以标明空子树的中根序列或后根序列构造一棵二叉树 为什么 BinaryTree BinaryTreebitree 深拷贝 BinaryNodecopy BinaryNodep if p null returnnull BinaryNodeq newBinaryNode p data q left copy p left 复制左子树q right copy p right 复制右子树returnq 习题解答 二叉树的二叉链表实现 6 2二叉树 广义表表示建立二叉树 以广义表形式可以表示一棵树 但不能唯一表示一棵二叉树 因为无法明确左右子树二叉树的广义表表示语法如下图 其中元素表示结点 表示空子树从上可知 二叉树的广义表表示是递归定义的 二叉树的二叉链表实现 6 2二叉树 广义表表示建立二叉树的示例如下 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 习 22画出用以下广义表形式表示的一棵二叉树 习题解答 A B C D F G J E H K L I M 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 1 输出二叉树的广义表表示publicvoidprintGenList privatevoidprintGenList BinaryNodep 1 广义表表示publicvoidprintGenList 输出二叉树的广义表表示字符串 System out print 二叉树的广义表表示 printGenList this root System out println 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 输出以p结点为根的一棵子树的广义表表示字符串 先根次序遍历 递归算法privatevoidprintGenList BinaryNodep if p null 若二叉树空System out print 输出空子树标记else System out print p data toString 访问当前结点if p left null p right null 非叶子结点 有子树 System out print printGenList p left 输出p的左子树 递归调用System out print printGenList p right 输出p的右子树 递归调用System out print 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 按广义表次序遍历序列建立二叉树 例6 2 二叉树的广义表表示 具体的实现思想就是上图privatestaticinti 0 publicstaticBinaryTreecreateByGenList Stringgenlist privatestaticBinaryNodecreate Stringgenlist 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 publicclassBinaryTree genlist privatestaticinti 0 publicstaticBinaryTreecreateByGenList Stringglist 以广义表表示构造二叉树 BinaryTreebitree newBinaryTree i 0 if glist length 0 bitree root create glist 创建子树 子树根值是glist 0 returnbitree 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 以广义表表示创建一棵子树 子树根值是glist i 返回根结点 递归方法privatestaticBinaryNodecreate Stringglist BinaryNodep null charch glist charAt i if ch A 空串返回null 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 publicclassBinaryTree 例6 2 publicstaticvoidmain Stringargs Stringgenlist AA BB DD G C E F H 图6 18所示二叉树的广义表表示 genlist A B C genlist A B C D F G J E H K L I M BinaryTreebitree BinaryTrees createByGenList genlist bitree printGenList 输出二叉树的广义表表示字符串 习题6 System out println 是否完全二叉树 bitree isCompleteBinaryTree 广义表表示建立二叉树 二叉树的二叉链表实现 6 2二叉树 以完全二叉树的层次遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 性质5 一棵具有n个结点的完全二叉树 对序号为i 0 i n 的结点 有 若i 0 则i为根结点 无父母结点 若i 0 则i的父母结点序号为 i 1 2 若2i 1 n 则i的左孩子结点序号为2i 1 否则i无左孩子 若2i 2 n 则i的右孩子结点序号为2i 2 否则i无右孩子 以完全二叉树的层次遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 二叉链表表示的完全二叉树类 继承二叉树类publicclassCompleteBinaryTreeextendsBinaryTree publicCompleteBinaryTree 构造空二叉树 super 以完全二叉树的层次序列构造完全二叉树 levellist指定层次序列publicCompleteBinaryTree T levellist this root create levellist 0 创建以levellist i 为根的一棵子完全二叉树 返回所建子树的根结点privateBinaryNodecreate T levellist inti BinaryNodep null if i levellist i 创建叶子结点p left create levellist 2 i 1 创建p的左子树p right create levellist 2 i 2 创建p的右子树 returnp 以完全二叉树的层次遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 publicstaticvoidmain Stringargs 图6 10所示完全二叉树的层次遍历序列String levellist A B C D E F G H CompleteBinaryTreecbitree newCompleteBinaryTree levellist cbitree preOrder cbitree inOrder cbitree postOrder 习题6System out println 是否完全二叉树 cbitree isCompleteBinaryTree 以完全二叉树的层次遍历序列建立二叉树 二叉树的二叉链表实现 6 2二叉树 二叉树遍历非递归算法 中根遍历 进行中根遍历时 当前结点的左子树被访问完后 没有办法到达当前结点及右子树 所以在进行当前结点的左子树的遍历前 需要用堆栈保存当前结点 进行中根遍历时 当前结点是栈顶元素时 在堆栈中存储越深的元素 就是当前结点的越远的祖先结点 越需要最后访问 也就是说 在从根到叶子结点的一条路径上 所经过结点的次序与返回结点的次序相反 二叉树的二叉链表实现 6 2二叉树 第一个结点 由于中序遍历首先考虑的元素是根结点的最左子孙结点 所以第一个结点要从根结点开始 一直到最左边的子孙结点为止的所有结点都压入堆栈 二叉树遍历非递归算法 中根遍历 二叉树的二叉链表实现 6 2二叉树 下一个结点 先弹出当前结点然后找遍历过程中的下一个元素 有两种情况 如果当前的结点有右子树 则此结点的右子树都未被访问 这时应该将右子结点 以及右子结点的所有左子孙结点全部入栈 下一个应该考虑的结点是从右子树开始的最左边子孙结点 如果当前结点没有右子树 则以当前结点为根的子树已经完全访问过了 下一个应该考虑的结点是前一个当前结点最近的未访问的祖先结点 其中 前一个当前结点就是刚刚出现在栈顶的结点 二叉树遍历非递归算法 中根遍历 二叉树的二叉链表实现 6 2二叉树 堆栈状态变化过程 HDBA DBA LIBA IBA BA EA MJA JA A KFC NFC FC C G 二叉树遍历非递归算法 中根遍历 二叉树的二叉链表实现 6 2二叉树 二叉树遍历非递归算法 中根遍历 二叉树的二叉链表实现 6 2二叉树 二叉树中根次序遍历的非递归算法描述如下 设置一个栈状态为空 从二叉树的根结点p开始 如果p不空或栈不空时 循环执行以下操作 直到走完二叉树且栈为空状态 如果p不空 表示刚刚到达一个结点 将p结点入栈 进入左子树 如果p为空并且栈不空 表示已走出一条路径 此时必须返回寻找另一条路径 而返回的结点就是刚才经过的最后一个结点 它已保存在栈顶 所以由p指向出栈的结点 访问p结点 再进入p的右子树 二叉树遍历非递归算法 中根遍历 二叉树的二叉链表实现 6 2二叉树 publicvoidinorderTraverse 中根次序遍历二叉树的非递归算法 System