六树和叉树.pptVIP

第六章 树和二叉树 第六章 树和二叉树 第六章 树和二叉树 6.1 树的定义和基本术语 6.2 二 叉 树 6.3 遍历二叉树和线索二叉树 遍历的应用 6.4 树和森林 后序(根)遍历（LRD） 若二叉树非空（1）后序遍历左子树（2）后序遍历右子树 （3）访问根结点 后序遍历序列： D,G,E,B,F,C,A 例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按LRD的顺序遍历左子树 （2）后序遍历右子树：即按LRD的顺序遍历右子树 （3）访问根结点A A F G E D C B e d c b f a + * / - - 先序(根)遍历序列：-,+,a,*,b,-,c,d,/,e,f 中序(根)遍历序列：a,+,b,*,c,-,d,-,e,/,f 后序(根)遍历序列：a,b,c,d,-,*,+,e,f,/,- 人们喜欢中序形式的算术表达式,对于计算机,使用后序易于求值 例：先中序遍历序遍历、中序遍历、后序遍历下图所示的二叉树 这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分： 1）基本项（也叫终止项）； 2）递归项 若二叉树非空 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树； 先序遍历递归定义 递归项 遍历的递归算法 上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例： 先序遍历（DLR）的定义： 该定义隐含着若二叉树为空，结束 上面先序遍历的定义等价于： 若二叉树为空，结束 ——基本项（也叫终止项） 若二叉树非空 ——递归项 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树； 下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit( )访问结点总是成功的。 先序遍历递归算法?void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) {//采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法先序 //遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) { //若二叉树为空，结束返回 , 若二叉树不为空， //访问根结点；遍历左子树，遍历右子树 Visit(T-data)；  PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit);  }//PreOrderTraverse 最简单的Visit函数是： Status PrintElement(TElemType e) {//输出元素e的值 printf(e); return OK; } ∧ D A B ∧ C ∧ ∧ E ∧ ∧ F ∧ T 2 中序遍历递归算法 ?void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) { //采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中序 //遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) { //若二叉树为空，结束返回  //若二叉树不为空，遍历左子树，访问根结点，遍历右子树 InOrderTraverse(T-lchild, Visit); Visit(T-data)；  InOrderTraverse(T-rchild, Visit); }// InOrderTraverse 你能写出后序遍历递归算法了吧 3 后序遍历递归算法 ?void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { //采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中序 //遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) { //若二