〈新〉遍历二叉树.ppt

基本二叉树操作 和二叉树有关的操作（1）构造一棵空二叉树（2）判断一棵二叉树是否空二叉树（3）返回二叉树中的结点数（4）返回二叉树的高度（5）清空一个已经存在的二叉树（6）在二叉树中插入结点（7）在二叉树中删除结点（8）遍历一棵二叉树 遍历二叉树 遍历二叉树 按某种路径(或策略)访问二叉树中的每个结点，且对每个结点只访问一次。这样，二叉树中的结点按被访问顺序形成一个线性序列。 用于信息查询或逐一处理，是二叉树大部分其他操作的基础 遍历二叉树 二叉树的三个基本单元 根结点、左子树、右子树 符号约定 L：表示遍历左子树 D：表示访问根结点 R：表示遍历右子树 对二叉树的可能遍历顺序 DLR, LDR, LRD, DRL, RDL, RLD六种 若限定先左后右，则有DLR, LDR, LRD三种，分别称之为先序遍历，中序遍历和后序遍历，形成先序序列，中序序列和后序序列 遍历二叉树的操作 先序遍历二叉树(PreOrderTraverse) 访问根结点 先序遍历左子树 先序遍历右子树 中序遍历二叉树(InOrderTraverse) 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历二叉树(PostOrderTraverse) 后序遍历左子树 后序遍历右子树 访问根结点 遍历二叉树的操作 遍历二叉树的操作 遍历二叉树的操作 遍历二叉树的操作 遍历二叉树的算法 算法实现 递归实现 非递归实现 二叉树的存储结构 采用二叉链表结构 遍历二叉树的递归算法 遍历二叉树的递归算法 遍历二叉树的递归算法 按先序序列建立二叉树的算法 按先序序列建立二叉树的算法 输入A B C _ _ D E _ G _ _ F _ _ _ 生成的二叉树及其存储结构为 按先序序列建立二叉树的算法 若希望建立如下二叉树对应的存储结构，应输入的字符序列是 几个问答 具有n个结点的不同形态的二叉树有多少棵？ 有 棵，如n=3时，有5种不同形态 已知结点先序序列和中序序列，是否可以唯一地确定一棵二叉树？ 能，如先序序列ABCDEFG，中序序列CBEDAFG，对应的二叉树为 几个问答 已知结点先序序列和后序序列，是否可以唯一地确定一棵二叉树？ 不能， 如先序序列ABCK，后序序列BKCA 已知结点中序序列和后序序列，是否可以唯一地确定一棵二叉树？ 能，如中序序列BKCA，后序序列BKCA 作业 1.分别按先序、中序和后序顺序列出下图二叉树的结点序列 2.用递归算法实现：交换二叉树中所有结点的左右子树。如： * 和具体的应用有关 D L R A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历: A D B C L R D L R D L R D A D C L R D 后序遍历序列： D B C A 后序遍历: B - + / a * b - e f c d 先序遍历： 中序遍历： 后序遍历： 层次遍历： - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f A B C 先序序列：ABC 中序序列：BAC 后序序列：BCA 先序序列：ABDCEFGH 中序序列：DBAFEGCH 后序序列：DBFGEHCA A B G D C E H F - + / a * e f b - c d 先序序列：-+a*b-cd/ef (前缀表达式) 中序序列：a+b*c-d-e/f (中缀表达式) 后序序列：abcd-*+ef/- (后缀表达式) A B C D 先序序列： 中序序列： 后序序列： 先序序列： 中序序列： 后序序列： A B G C D E F A B C D 先序序列：ABCD 中序序列：DCBA 后序序列：DCBA 先序序列：ABCDEGF 中序序列：CBEGDFA 后序序列：CGEFDBA A B G C D E F Make a BT uniquely by preorder and inorder Example: preorder { ABHFDECKG } and inorder { HBDFAEKCG }, make a