第07章_二叉树2011_919.ppt

二叉树 7 1二叉树的基本概念7 2二叉树的基本运算7 3二叉树的存储结构7 3 1顺序存储7 3 2链式存储7 4二叉树的遍历7 4 1二叉树遍历的定义7 4 2二叉树遍历的递归实现7 4 3二叉树遍历的非递归实现 7 5二叉树其他运算的实现7 7树 森林到二叉树的转换7 7 1树 森林到二叉树的转换7 7 2二叉树到树 森林的转换 7 1二叉树的基本概念二叉树的定义为 二叉树是一个由结点构成的有限集合 这个集合或者为空 或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成 当二叉树的结点集合为空时 称为空二叉树 a b e d c h f g 二叉树有以下五种基本形态 a 空二叉树 d 根和空左子树 非空右子树 b 根和空的左 右子树 c 根和非空左子树 空右子树 e 根和非空的左 右子树 树型结构中使用的术语如父母 双亲或前件 子女 后件 祖先 子孙 兄弟和路径等在二叉树中仍然可以沿用 但值得注意的是 二叉树并非一般树型结构的特殊形式 它们为两种不同的数据结构 二叉树与一般树型结构的主要区别在于 1 二叉树中每个非空结点最多只有两个子女 而一般的树型结构中每个非空结点可以有0到多个子女 2 二叉树中结点的子树要区分左子树和右子树 即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树 二叉树具有以下重要性质 性质1一棵非空二叉树的第i层上至多有2i 1个结点 i 1 证明 当i 1时 只有根结点 此时21 1 20 1 显然上述性质成立 又由于在二叉树中每个结点最多只能具有两子女 因而第i 1层上结点的最大个数是第i层上结点的最大个数的两倍 于是第2层上结点的最大个数为2 第3层上结点的最大个数为4 则第i层上结点的最大个数即为2i 1 性质2深度为h的二叉树至多有2h 1个结点 h 1 根据性质1 深度为h的二叉树最多具有的结点的个数为20 21 22 2h 1 2h 1 性质3对于任何一棵二叉树T 如果其终端结点数为n0 度为2的结点数为n2 则n0 n2 1 证明 假设二叉树中总的结点个数为n 度为1的结点个数为n1 则有 n n0 n1 n2又由于在二叉树中除根结点外 其它结点均通过一条树枝且仅通过一条树枝与其父母结点相连 即除根结点外 其它结点与树中的树枝存在一一对应的关系 而二叉树中树枝的总条数为n1 2 n2 因而二叉树总结点的个数为 n n1 2 n2 1于是有 n0 n1 n2 n1 2 n2 1显然n0 n2 1成立 如果一棵二叉树中所有终端结点均位于同一层次 而其它非终端结点的度数均为2 则称此二叉树为满二叉树 在满二叉树中 若其深度为h 则其所包含的结点个数必为2h 1 下图中的二叉树即为一棵深度为3的满二叉树 其结点的个数为23 1 7 1 4 2 5 3 6 7 如果一棵二叉树扣除其最大层次那层后即成为一棵满二叉树 且层次最大那层的所有结点均向左靠齐 则称该二叉树为完全二叉树 通俗地说 完全二叉树中只有最下面的两层结点的度数可以小于2 且最下面一层的结点都集中在该层最左边的若干位置上 下图所示的二叉树即为一棵深度为3的完全二叉树 若对深度相同的满二叉树和完全二叉树中的所有结点按自上而下 同一层次按自左向右的顺序依次编号 则两者对应位置上的结点编号应该相同 1 4 2 5 3 6 对于完全二叉树 具有以下性质 性质4对于具有n个结点的完全二叉树 如果按照从上到下 同一层次上的结点按从左到右的顺序对二叉树中的所有结点从1开始顺序编号 则对于序号为i的结点 有 1 如果i 1 则序号为i的结点其双亲结点的序号为 i 2 i 2 表示不大于i 2的最大整数 如果i 1 则结点i为根结点 没有双亲 2 如果2i n 则结点i无左子女 此时结点i为终端结点 否则其左子女为结点2i 3 如果2i 1 n 则结点i无右子女 否则其右子女为结点2i 1 二叉树 7 1二叉树的基本概念7 2二叉树的基本运算7 3二叉树的存储结构7 3 1顺序存储7 3 2链式存储7 4二叉树的遍历7 4 1二叉树遍历的定义7 4 2二叉树遍历的递归实现7 4 3二叉树遍历的非递归实现 7 5二叉树其他运算的实现7 7树 森林到二叉树的转换7 7 1树 森林到二叉树的转换7 7 2二叉树到树 森林的转换 7 2二叉树的基本运算ADTbintree 数据对象D D是具有相同性质的数据元素构成的集合 数据关系R 如果D为空或D仅含一个元素 则R为空 否则D中存在一个特殊的结点root 称之为根结点 其无前驱 其它结点被分成互不相交的两个集合 分别构成root的左子树l和右子树r 若l和r非空 则它们的根结点lroot和rroot分别称为整棵二叉树根结点root的后继结点 左子树l和右子树r也是二叉树 因而它们中数据元素间的关系也同样满足R的定义 二叉树的基本操作如下 1 createbitree t 2 destroybitree t 3 root t 4 leftchild t 5 rightchild t 6 locate t x 7 parent t x 8 isempty t 9 depth t 10 numofnode t 11 addchild t x t1 b 12 deletechild t x b 13 setnull t 14 isequal t1 t2 15 preorder t 16 inorder t 17 postorder t 18 transform1 F t 19 transform2 t F ADTbintree 二叉树 7 1二叉树的基本概念7 2二叉树的基本运算7 3二叉树的存储结构7 3 1顺序存储7 3 2链式存储7 4二叉树的遍历7 4 1二叉树遍历的定义7 4 2二叉树遍历的递归实现7 4 3二叉树遍历的非递归实现 7 5二叉树其他运算的实现7 7树 森林到二叉树的转换7 7 1树 森林到二叉树的转换7 7 2二叉树到树 森林的转换 7 3二叉树的存储结构二叉树常用的存储结构有两种 顺序存储结构和链式存储结构 7 3 1顺序存储结构顺序存储结构是使用一组连续的空间存储二叉树的数据元素和数据元素之间的关系 因此必须将二叉树中所有的结点排成一个适当的线性序列 在这个线性序列中应采用有效的方式体现结点之间的逻辑关系 a b d e c f 01234567 a 完全二叉树 1 完全二叉树的顺序存储对于一棵具有n个结点的完全二叉树 我们可以按从上到下 同一层次按从左到右的顺序依次将结点存入一个一维数组中 根据上述性质4 无须附加任何其它信息就能根据每个结点的下标找到它的子女结点和双亲结点 b 完全二叉树的顺序存储 完全二叉树顺序存储的头文件 defineMAXSIZE20typedefchardatatype 二叉树结点值类型 datatypetree MAXSIZE intn 树中实际所含结点的个数 2一般二叉树的顺序存储由于二叉树中每个结点最多只有两个子女 于是存储一个结点时 除了包含结点本身的属性值外 另外增加两个域 分别用来指向该结点的两个子女在数组中的下标 二叉树顺序存储的头文件 defineMAXSIZE20typedefchardatatype 结点值的类型 typedefstruct datatypedata intlchild rchild node 二叉树结点的类型 nodetree MAXSIZE intn 树中实际所含结点的个数 introot 存放根结点的下标 带双亲指示的二叉树顺序存储的头文件 defineMAXSIZE20typedefchardatatype 结点值的类型 typedefstruct datatypedata intlchild rchild intparent 存放双亲结点的下标 node 二叉树结点的类型 nodetree MAXSIZE intn 树中实际所含结点的个数 introot 存放根结点的下标 7 3 2链式存储结构二叉树的链式存储方式下每个结点也包含三个域 分别记录该结点的属性值及左 右子树的位置 与顺序存储结构不同的是 其左 右子树的位置不是通过数组的下标 而是通过指针方式体现 如下图所示 a b d c g f e a g f e d root a 一棵二叉树 b 二叉树的链式存储 二叉树链式存储头文件 typedefchardatatype 结点属性值的类型 typedefstructnode 二叉树结点的类型 datatypedata structnode lchild rchild bintnode typedefbintnode bintree bintreeroot 指向二叉树根结点的指针 带双亲指针的二叉树链式存储的头文件 typedefchardatatype 结点属性值的类型 typedefstructnode 二叉树结点的类型 datatypedata structnode lchild rchild structnode parent 指向双亲的指针 bintnode typedefbintnode bintree bintreeroot 指向二叉树根结点的指针 二叉树 7 1二叉树的基本概念7 2二叉树的基本运算7 3二叉树的存储结构7 3 1顺序存储7 3 2链式存储7 4二叉树的遍历7 4 1二叉树遍历的定义7 4 2二叉树遍历的递归实现7 4 3二叉树遍历的非递归实现 7 5二叉树其他运算的实现7 7树 森林到二叉树的转换7 7 1树 森林到二叉树的转换7 7 2二叉树到树 森林的转换 7 4二叉树的遍历7 4 1二叉树遍历的定义所谓二叉树的遍历 是指按一定的顺序对二叉树中的每个结点均访问一次 且仅访问一次 按照根结点访问位置的不同 通常把二叉树的遍历分为三种 前序遍历 中序遍历和后序遍历 1 二叉树的前序遍历首先访问根结点 然后按照前序遍历的顺序访问根结点的左子树 再按照前序遍历的顺序访问根结点的右子树 a b d f e g c 前序遍历 abdefgc中序遍历 debgfac后序遍历 edgfbca 2 二叉树的中序遍历按照中序遍历的顺序访问根结点的左子树 然后访问根结点 按照中序遍历的顺序访问根结点的右子树 3 二叉树的后序遍历首先按照后序遍历的顺序访问根结点的左子树 然后按照后序遍历的顺序访问根结点的右子树 最后访问根结点 前序遍历 ABCDFEGH中序遍历 BAFDCGEH后序遍历 BFDGHECA 前序遍历 ABDHIEJCFG中序遍历 HDIBJEAFCG后序遍历 HIDJEBFGCA 7 4 2二叉树遍历的递归实现由于二叉树的遍历是递归定义的 因此采用递归方式实现二叉树遍历的算法十分方便 只要按照各种遍历规定的次序 访问根结点时就输出根结点的值 访问左子树和右子树时进行递归调用即可 1 前序遍历二叉树的递归算法voidpreorder bintreet if t printf c t data preorder t lchild preorder t rchild 2 中序遍历二叉树的递归算法voidinorder bintreet if t inorder t lchild printf c t data inorder t rchild 3 后序遍历二叉树的递归算法voidpostorder bintreet if t postorder t lchild postorder t rchild printf c t data 4 二叉树的创建算法利用二叉树前序遍历的结果可以非常方便地生成给定的二叉树 具体做法是 将第一个输入的结点作为二叉树的根结点 后继输入的结点序列是二叉树左子树前序遍历的结果 由它们生成二叉树的左子树 再接下来输入的结点序列为二叉树右子树前序遍历的结果 应该由它们生成二叉树的右子树 而由二叉树左子树前序遍历的结果生成二叉树的左子树和由二叉树右子树前序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的前序遍历结果生成该二叉树的过程完全相同 只是所处理的对象范围不同 于是完全可以使用递归方式加以实现 根据前序遍历结构创建一颗给定二叉树 voidcreatebintree bintree t charch if ch getchar t NULL else t bintnode malloc sizeof bintnode 生成二叉树的根结点 t data ch createbintree 递归实现右子树的建立 7 4 3二叉树遍历的非递归实现在第5章 已经介绍了由递归程序转换成非递归程序的两种方法 简单递归程序的转换和复杂递归程序的转换 二叉树的遍历问题应该属于后者 即在采用非递归方式实现二叉树遍历时 必须使用一个堆栈记录回溯点 以便将来进行回溯 以下为一个顺序栈的定义及其部分操作的实现 typedefstructstack 栈结构定义 bintreedata 100 inttag 100 为栈中每个元素设置的标记 用于后序遍历 inttop 栈顶指针 seqstack voidpush seqstack s bintreet 进栈 s data s top t bintreepop seqstack s 出栈 if s top 1 s top return s data s top 1 elsereturnNULL 1 二叉树前序遍历的非递归实现前序遍历一棵非空树t时 访问完t的根结点后 就应该进入t的左子树 但此时必须将t保存起来 以便访问完其左子树后 进入其右子树的访问 即在t处必须设置一个回溯点 对t的左子树和右子树的遍历也是如此 仔细观察不难发现 这些回溯点应该使用栈来进行管理 在整个二叉树前序遍历的过程中 程序要做的工作始终分成两个部分 当前正在处理的树 子树 和保存在栈中待处理的部分 只有这两部分的工作均完成后 程序方能结束 voidpreorder1 bintreet 非递归实现二叉树的前序遍历 seqstacks s top 1 while t s top 1 当前处理的子树不为空或栈不为空则循环 while t printf c t data s top s data s top t t t lchild if s top 1 t pop 2 二叉树中序遍历的非递归实现中序遍历一棵非空树t时 首先应该进入t的左子树访问 此时由于t的根结点及右子树尚未访问 因此必须将t保存起来 放入栈中 以便访问完其左子树后 从栈中取出t 进行其根结点及右子树的访问 对t的左子树和右子树的遍历也是如此 在整个二叉树中序遍历的过程中 程序要做的工作始终分成两个部分 当前正在处理的树 子树 和保存在栈中待处理的部分 只有这两部分的工作均完成后 程序方能结束 voidinorder1 bintreet seqstacks s top 1 while t NULL s top 1 while t push 3 二叉树后序遍历的非递归实现后序遍历一棵非空树t时 首先应该进入t的左子树访问 此时由于t的右子树及根结点尚未访问 因此必须将t保存在栈中 以便访问完其左子树后 从栈中取出t 进行其右子树及根结点的访问 值得注意的是 当一个元素位于栈顶即将被处理时 其左子树的访问一定已经完成 如果其右子树尚未遍历 接下来应该进入其右子树的访问 而此时该栈顶元素是不能出栈的 因为其根结点还未被访问 只有等到其右子树也访问完成后 该栈顶元素才能出栈 并输出其根结点的值 因此一个元素位于栈顶时 必须设法识别其右子树是否已被访问 解决的方法为 使用seqstack类型中的数组tag 用于标识栈中每个元素的状态 每个元素刚进栈时 其tag值初始化为0 当某一元素位于栈顶即将被处理时 1 如果其tag值为0 意味着其右子树尚未访问 于是将其右子树作为当前处理的对象 此时该栈顶元素仍应该保留在栈中 并将其tag的值改为1 2 如果其tag值为1 意味着其右子树已被访问 接下来应该访问其根结点 并将其出栈 在整个二叉树后序遍历的过程中 程序要做的工作始终分成两个部分 当前正在处理的树 子树 和保存在栈中待处理的部分 只有这两部分的工作均完成后 程序方能结束 voidpostorder1 bintreet seqstacks s top 1 while t s top 1 while t s top s data s top t s tag s top 0 t t lchild while s top 1 二叉树 7 1二叉树的基本概念7 2二叉树的基本运算7 3二叉树的存储结构7 3 1顺序存储7 3 2链式存储7 4二叉树的遍历7 4 1二叉树遍历的定义7 4 2二叉树遍历的递归实现7 4 3二叉树遍历的非递归实现 7 5二叉树其他运算的实现7 7树 森林到二叉树的转换7 7 1树 森林到二叉树的转换7 7 2二叉树到树 森林的转换 7 5二叉树其它运算的实现由于二叉树本身的定义是递归的 因此关于二叉树的许多问题或运算采用递归方式实现非常地简单和自然 1 二叉树的查找locate t x bintreelocate bintreet datatypex bintreep if t NULL returnNULL elseif t data x returnt else p locate t lchild x if p returnp elsereturnlocate t rchild x 2 统计二叉树中结点的个数numofnode t intnumofnode bintreet if t NULL return0 elsereturn numofnode t lchild numofnode t rchild 1 3 判断二叉树是否等价isequal t1 t2 intisequal bintreet1 bintreet2 intt t 0 if t1 NULL 4 求二叉树的高 深 度depth t intdepth bintreet inth lh rh if t NULL h 0 else lh depth t lchild 求左子树的高度 rh depth t rchild 求左子树的高度 if lh rh h lh 1 求二叉树t的高度 elseh rh 1 returnh 二叉树 7 1二叉树的基本概念7 2二叉树的基本运算7 3二叉树的存储结构7 3 1顺序存储7 3 2链式存储7 4二叉树的遍历7 4 1二叉树遍历的定义7 4 2二叉