二叉树的遍历和应用.ppt

1 二叉树的遍历和应用 数据结构与算法 2 预备知识 递归 3 什么是递归 递归是极强大的问题解决技术 当一个函数用它自己来定义时就是递归 递归将一个复杂问题分解为一些更小的问题 4 举例 查词典 顺序查找 可以从词典第一页开始 按顺序查找每个单词 直到找到 递归解决方案 分而治之的策略 把问题划分成小问题 直到到达基例 查找词典 查找词典的前半部分 查找词典的后半部分 5 递归解决方案的一般形式 怎样按同类型的更小的问题来定义问题各个递归调用怎么减小问题规模哪个问题实例可用做基例随着问题规模的减小 最终能否到达基例 6 举例1 n的阶乘 publicstaticintfact intn computethefactorialofanonnegativeinteger precondition nmustbegreaterthanorequalto0 postcondition returnsthefactorialofn if n 0 return1 Else returnn fact n 1 endif endfact 7 举例2 逆置字符串 减小规模 去掉最后一个字符writeBackward s if thestringsisempty donothing thisisthebasecase Else WritethelastcharacterofswriteBackward sminusitslastcharacter endif end 减小规模 去掉第一个字符writeBackward2 s if thestringsisempty donothing thisisthebasecase Else writeBackward2 sminusitsfirstcharacter Writethefirstcharacterofs endif end 8 举例3 Hanoi塔 solveTowers count source destination spare if countis1 Moveadiskdirectlyfromsourcetodestination Else sloveTowers count 1 source spare destination sloveTowers 1 source destination spare sloveTowers count 1 spare destination source endif end 9 举例4 兔子繁殖 递归法 publicstaticintrabbit intn if n 2 return1 Else returnrabbit n 1 rabbit n 2 endif end rabbit n 1n 1或n 2 rabbit n 1 rabbit n 2 n 2 10 举例4 兔子繁殖 迭代法 publicstaticintiterativeRabbit intn iterativesolutiontotherabbitproblem initializebasecases intprevious 1 rabbit 1 intcurrent 1 rabbit 2 intnext 1 resultwhennis1or2 computernextrabbitvalueswhenn 3for inti 3 i n i next current previous previous current current next endforreturnnext end 11 二叉树的遍历 12 一 问题的提出 二 遍历算法 三 算法的递归描述 四 遍历算法的应用举例 13 顺着某一条搜索路径巡访二叉树中的结点 使得每个结点均被访问一次 而且仅被访问一次 问题的提出 访问 的含义可以很广 如 输出结点的信息等 14 遍历 是任何类型均有的操作 对线性结构而言 只有一条搜索路径 因为每个结点均只有一个后继 故不需要另加讨论 而二叉树是非线性结构 每个结点有两个后继 则存在如何遍历即按什么样的搜索路径遍历的问题 15 层次遍历 首先创建一个队列 若二叉树非空 将根放入队列 从队列取出一个元素并访问 如果该元素有左孩子就将它放入队列 如果该元素有右孩子就将它放入队列 若队列非空 继续第2步 直至队列为空 则二叉树的层次遍历过程结束 例如 图5 1中的二叉树按照层次遍历的结果为 ABCDEFGHI 16 前序周游 preordertraversal 若二叉树非空 则依次进行如下操作 1 访问根结点 2 前序周游左子树 3 前序周游右子树 前序遍历二叉树 preordertraversal 例如 图5 1中的二叉树按照前序周游的结果为 ABDCEGFHI 17 中序周游 inordertraversal 若二叉树非空 则依次进行如下操作 1 中序周游左子树 2 访问根结点 3 中序周游右子树 中序遍历二叉树 inordertraversal 例如 图5 1中的二叉树按照中序周游的结果为 BDAGECHFI 18 后序周游 postordertraversal 若二叉树非空 则依次进行如下操作 1 后序周游左子树 2 后序周游右子树 3 访问根结点 后序遍历二叉树 postordertraversal 例如 图5 1中的二叉树按照后序周游的结果为 DBGEHIFCA 19 已知二叉树的前序和中序周游序列如下 画出该二叉树 前序周游序列 ABCDEFGHIJ中序周游序列 CBEDAGHFJI 课堂练习 20 已知二叉树的后序和中序周游序列如下 画出该二叉树 后序周游序列 ABCDEFG中序周游序列 ACBGEDF 课堂练习 21 画出中序周游序列为ABCDEFGHIJKL的完全二叉树 课堂练习 22 上面三种周游方法都可以用递归函数来实现例如 前序周游二叉树的函数为 voidpreorder BinNode subroot if subroot NULL return visit subroot preorder subroot left preorder subroot right 遍历二叉树的递归实现 23 课后思考 思考遍历算法的非递归算法思想描述 由先序 中序和后序中任意两个序列能够唯一确定一颗二叉树 24 遍历算法的应用举例 1 统计二叉树中叶子结点的个数 先序遍历 2 求二叉树的深度 后序遍历 3 复制二叉树 后序遍历 4 建立二叉树的存储结构 25 1 统计二叉树中叶子结点的个数 算法基本思想 先序 或中序或后序 遍历二叉树 在遍历过程中查找叶子结点 并计数 由此 需在遍历算法中增添一个 计数 的参数 并将算法中 访问结点 的操作改为 若是叶子 则计数器增1 26 voidCountLeaf BiTreeT int if CountLeaf 27 TraversalExample Returnthenumberofnodesinthetreetemplateintcount BinNode subroot if subroot NULL return0 Nothingtocountif subroot isleaf return1 thenodeisleafreturncount subroot left count subroot right 28 2 求二叉树的深度 算法基本思想 从二叉树深度的定义可知 二叉树的深度应为其左 右子树深度的最大值加1 由此 需先分别求得左 右子树的深度 算法中 访问结点 的操作为 求得左 右子树深度的最大值 然后加1 首先分析二叉树的深度和它的左 右子树深度之间的关系 29 求二叉树的深度的伪代码设计 请利用上课讲述的方法设计出该问题的详细算法 多写几个 课后复习 30 二叉树的存储 31 存于顺序存储结构 32 以字符串的形式根左子树右子树定义一棵二叉树 例如 A B C D 以空白字符 表示 A B C D 空树 只含一个根结点的二叉树 A 以字符串 A 表示 以下列字符串表示 33 StatusCreateBiTree BiTree CreateBiTree 34 ABCD A B C D 上页算法执行过程举例如下 A T B C D 35 仅知二叉树的先序序列 abcdefg 不能唯一确定一棵二叉树 由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列 cbdaegf 则会如何 二叉树的先序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 36 abcdefg cbdaegf 例如 a a b b c c d d e e f f g g a b c d e f g 先序序列中序序列 37 voidCrtBT BiTreeelse CrtBT 38 T BiTNode malloc sizeof BiTNode T data pre ps if k is T Lchild NULL elseCrtBT T Lchild pre ino ps 1 is k is if k is n 1 T Rchild NULL elseCrtBT T Rchild pre ino ps 1 k is k 1 n k is 1 39 二叉树的线索化 40 何谓线索二叉树 遍历二叉树的结果是 求得结点的一个线性序列 A B C D E F G H K 例如 先序序列 ABCDEFGHK 中序序列 BDCAHGKFE 后序序列 DCBHKGFEA 41 指向该线性序列中的 前驱 和 后继 的指针 称作 线索 与其相应的二叉树 称作 线索二叉树 包含 线索 的存储结构 称作 线索链表 ABCDEFGHK D C B E 42 在二叉链表的结点中增加两个标志域 并作如下规定 data LTag RTag LChild RChild LTag RTag 0LChild域指示结点的左孩子 1LChild域指示结点的前驱 0RChild域指示结点的右孩子 1RChild域指示结点的后继 43 在中序遍历过程中修改结点的左 右指针域 以保存当前访问结点的 前驱 和 后继 信息 遍历过程中 附设指针pre 并始终保持指针pre指向当前访问的 指针p所指结点的前驱 如何建立线索链表 44 45 voidInThreading BiThrTreep if p 对以p为根的非空二叉树进行线索化InThreading p lchild 左子树线索化if p lchild 建前驱线索 p LTag Thread p lchild pre if pre rchild 建后继线索 pre RTag Thread pre rchild p pre p 保持pre指向p的前驱InThreading p rchild 右子树线索化 if InThreading 46 StatusInOrderThreading BiThrTree InOrderThreading 47 if T Thrt lchild Thrt else Thrt lchild T pre Thrt InThreading T pre rchild Thrt 处理最后一个结点pre RTag Thread Thrt rchild pre 48 父指针表示和等价类问题 49 父指针表示法 50 等价类问题 父指针表示法可以有效的解答下述问题 给出两个结点 它们是否在同一棵树中 ReturnTRUEifnodesindifferenttreesboolGentree differ inta intb introot1 FIND a Findrootforaintroot2 FIND b Findrootforbreturnroot1 root2 Compareroots 51 Union Find voidGentree UNION inta intb introot1 FIND a Findrootforaintroot2 FIND b Findrootforbif root1 root2 array root2 root1 intGentree FIND intcurr const while array curr ROOT curr array curr returncurr Atroot 52 等价类处理的例子 1 53 等价类处理的例子 2 54 重量权衡合并规则 需要降低树的高度 Weightedunionrule 两树归并时 将结点较少树的根结点指向结点较多树的根结点 可以把树的整体深度限制在O logn 55 路径压缩PathCompression intGentree FIND intcurr const if array curr ROOT returncurr returnarray curr FIND array curr 56 要点回顾 递归算法的设计方法二叉树的遍历算法二叉树遍历算法的应用二叉树的建立