数据结构 严蔚敏 -第6章 树和二叉树2-遍历二叉树(刘)

1、 刘灵丽 湘南学院 遍历二叉树遍历二叉树二二 几种遍历方法几种遍历方法1.先序遍历（先序遍历（DLR)： 若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则 (1)访问根结点访问根结点 (2)先序遍历左子树先序遍历左子树 (3)先序遍历右子树先序遍历右子树2.中序遍历：中序遍历：3.后序遍历：后序遍历：4.按层次遍历：从上到下、从左到右访问各结点。按层次遍历：从上到下、从左到右访问各结点。一一 什么叫遍历什么叫遍历 树中每个节点被访问有且仅有一次。树中每个节点被访问有且仅有一次。ADBCD L RAD L RD L RBDCD L R先序遍历序列：先序遍历序列：A B D C先序遍历:A

2、DBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:ADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:Bvoid preorder(BiTree T) if(T) printf(%c ,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTC

3、printf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C-+/a*b-efcd先序遍历：先序遍历：中序遍历：后序遍历：后序遍历：层次遍历：-+ a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f以字符串的形式表示一棵二叉树以字符串的形式表示一棵二叉树ABCD 以字符串“表示空树空树只含根结点的二只含根结点的二叉树叉树A 以字符串“ A 表示 以“ AB C D表示Status CreateBiTree(BiTree &T)

4、 scanf(&ch); if (ch= ) T = NULL; else T = (BiTNode *)malloc(sizeof(BiTNode); T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; A B C D A BCD上页算法执行过程举例如下：ATBCD1，根结点入栈，根结点入栈2，若栈空则转，若栈空则转83，while(栈顶元素不是空指针栈顶元素不是空指针)左孩子入栈左孩子入栈4，若栈顶元素为空指针，则空指针出栈，若栈顶元素为空指针，则空指

5、针出栈5，若栈不空，出栈，访问结点，若栈不空，出栈，访问结点6，右孩子入栈，右孩子入栈7，转，转28，returnvoid InorderTraverse(BiTree T, void (*Visit) (TelemType& e) /中序遍历二叉树中序遍历二叉树T T的非递归算法的非递归算法 Stack *S; InitStack(S); Push(S,T); while(!StackEmpty(S) while(Gettop(S,p)&p) Push(S,p-lchild);/左孩子入栈左孩子入栈 Pop(S,pPop(S,p) ) /空指针出栈空指针出栈 if(!StackEmpty(S

6、if(!StackEmpty(S) ) /访问结点访问结点 Pop(S,p); if(!Visit(pPop(S,p); if(!Visit(p-data) return ERROR;-data) return ERROR; Push(S,p-rchild Push(S,p-rchild);); /if /if / while return OK; 4 非递归算法实现中序遍历时栈的状态非递归算法实现中序遍历时栈的状态ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：C(4)pABCDEFGi

7、P-A访问：C B(5)ABCDEFGiP-AP-D访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：C Bp(7)ABCDEFGiP-AP-D访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：C B EP=NULL(9)ABCDEFGiP-A访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：C B E Gp(10)ABCDEFGiP-A访问：C B E G D Fp=NULL(13)ABCDEFGi访问：C B E G D F Ap(14)ABCDEFGi访问：C B E G D F Ap

8、=NULL(15)后序遍历非递归算法5.1 统计二叉树中叶子结点的个数统计二叉树中叶子结点的个数算法基本思想算法基本思想: : 先序先序( (或中序或后序或中序或后序) )遍历二叉树，在遍历二叉树，在遍历过程中查找叶子结点，并计数。遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个由此，需在遍历算法中增添一个“计数计数”的参数，并将算法中的参数，并将算法中“访问结点访问结点”的操的操作改为：若是叶子，则计数器增作改为：若是叶子，则计数器增1 1。5 遍历算法的应用举例遍历算法的应用举例void CountLeaf (BiTree T, int& count) if ( T ) if

9、(!T-lchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf5.2 求二叉树的深度求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的深二叉树的深度应为其左、右子树深度的最大值加度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右求得左、右子树深度的最大值，然后加子树深度的最大值，然后加

10、 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;以字符串的形式定义一棵二叉树以字符串的形式定义一棵二叉树ABCD以空白字符“ ”表示A(B( ,C(

11、, ),D( , )空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示Status CreateBiTree(BiTree &T) scanf(&ch); if (ch= ) T = NULL; else T = (BiTNode *)malloc(sizeof(BiTNode); T-data = ch; / 生成根结点 CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树 return OK; A B C D A BCD上页算法执行过程举例如下：ATBCDl可使用一个顺序存储的

12、队列可使用一个顺序存储的队列q100,存放存放还没有处理的子树的根结点的地址。注还没有处理的子树的根结点的地址。注意意,队首和队尾指针分别指向队首结点队首和队尾指针分别指向队首结点和下次进队结点的存放位置。和下次进队结点的存放位置。1) 首先把根节点入队。首先把根节点入队。2) 然后访问队头的一个结点，再把该结点然后访问队头的一个结点，再把该结点非空的左右子树入队。非空的左右子树入队。3) 如果队列不空，重复如果队列不空，重复2)。l 当用栈非递归实现树当用栈非递归实现树的先序遍历时，写出的先序遍历时，写出遍历右边所表示的树遍历右边所表示的树的全过程。像讲义中的全过程。像讲义中那样，写出遍历每一那样，写出遍历每一步栈中的数据。不是步栈中的数据。不是写具体的实现代码。写具体的实现代码。ABCDEFGl分别写一个函数，统计二叉树的节点个数；分别写一个函数，统计二叉树的节点个数；输出树的深度；最大元；最小元；输出树的深度；最大元；最小元；用树形结用树形结构打印出该二叉树。构打印出该二叉树。l提示