6.4二叉树的遍历算法描述.ppt

1、,6.4 二叉树的算法描述,Void lnorderTraverse(BiTree BT) 采用二叉链表存储结构，中序遍历二叉树T的非递归算法. InitStack(S)； p=BT； while(p|!StackEmpty(S) if(p) push(S，p)； p=p-lchild；/根指针进栈，遍历左子树 else 根指针退栈，访问根结点，遍历右子树 pop(S，p)； visit(p); p=p-rchild； /else InOrderTraverse,6.4.1非递归中序遍历BT的算法:,我们先观察一下三种遍历行走的路线,*,*,*,*,*,*,*,*,*,前序遍历NLR,#,#,

2、#,#,#,#,#,#,#,中序遍历LNR,三种遍历的访问位置对比：,三种遍历的路线完全一样，只是访问时间不同；,前序：第一次经过* 时访问,中序：第二次经过# 时访问,后序：第三次经过 push(S,p); pop(S,p); Boolean StackEmpty(S); 下面给出基于逻辑结构的算法描述,非递归中序遍历二叉树的算法思想 建立栈 stack； P指向根； 当p不空 且 stack 不空时反复做： 若 p不空 ,p 入 栈; p指向左子女； 否则： 出栈顶元素到p中； 访问p； p指向右子女； 4. 结束,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT

3、的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,非递归中序遍历BT的算法:,7/28/2020,二叉树与表达式：,表达式 : ( a + b ) c d / e 二叉树的先序遍历序列为： + a b c / d e 二叉树的中序遍历序列为： a + b c d / e 二叉树的后序遍历序列为： a b + c d e / ,前缀表达式 中缀表达式 后缀表达

4、式,void PreOrderTraverse (BiTree T, void (*visit) (TelemType / PreOrderTraverse,非递归先序遍历二叉树,6.4.2遍历算法的应用举例,1、查询二叉树中某个结点,7/28/2020,Status Preorderelem (BiTree T, ElemType x, BiTree ,7/28/2020,2、统计二叉树中叶子结点的个数,7/28/2020,算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点并计数。在遍历算法中增加一个参数用于计数，并将算法中“VISIT()” 的操作改为:若是叶子，则计

5、数器增1。,void CountLeaf (BiTree T, int / if / CountLeaf,3 按先序遍历序列建二叉树,Status CreateBiTree(BiTree / CreateBiTree,A B C D E G F ,按先序遍历序列建立二叉树的二叉链表， 已知先序序列为：,7/28/2020,4、求二叉树的深度,7/28/2020,int TreeDepth (BiTree T ) / 返回二叉树的深度 if ( !T ) depth = 0; else depthLeft = TreeDepth( T-lchild ); depthRight= TreeDepth( T-rchild ); depth = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depth; ,算法：,1 前序遍历序列：EDACBGFH