数据结构的课件实验六二叉树的遍历

实验六 二叉树的遍历操作1.实验内容 （1）先序遍历操作：访问根结点先序遍历左子树先序遍历右子树；包括递归算法和非递归算法。（2）中序遍历操作：中序遍历左子树访问根结点中序遍历右子树；包括递归算法和非递归算法。（3）后序遍历操作：后序遍历左子树后序遍历右子树访问根结点；包括递归算法和非递归算法。2.实现的步骤（1）实现将链式队列的遍历操作程序代码。（2）实现main主函数。3.程序代码完整清单#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/*数据元素*/struct node *lchild;/*指向左孩子*/struct node *rchild;/*指向右孩子*/ BTNode;/基本操作函数声明 void CreateBTNode(BTNode *&b,char *str); /*创建一棵二叉树*/ void DispBTNode(BTNode *b); /*输出二叉树*/ void PreOrder(BTNode *b); /*先序遍历的递归算法*/ void PreOrder1(BTNode *b); /*先序遍历的非递归算法1*/ void PreOrder2(BTNode *b); /*先序遍历的非递归算法2*/ void InOrder(BTNode *b); /*中序遍历的递归算法*/ void InOrder1(BTNode *b); /*中序遍历的非递归算法1*/ void InOrder2(BTNode *b); /*中序遍历的非递归算法2*/ void PostOrder(BTNode *b);/*后序遍历的递归算法*/ void PostOrder1(BTNode *b); /*后序遍历的非递归算法1*/ void PostOrder2(BTNode *b); /*后序遍历的非递归算法2*/ void TravLevel(BTNode *b); /*输出二叉树*/ void main()BTNode *b;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf( 二叉树b:);DispBTNode(b);printf(nn);printf( 层次遍历序列:);TravLevel(b);printf(n);printf( 先序遍历序列:n);printf( 递归算法:);PreOrder(b);printf(n);printf( 非递归算法1:);PreOrder1(b);printf(n);printf( 非递归算法2:);PreOrder2(b);printf(n);printf( 中序遍历序列:n);printf( 递归算法:);InOrder(b);printf(n);printf( 非递归算法1:);InOrder1(b);printf(n);printf( 非递归算法2:);InOrder2(b);printf(n);printf( 后序遍历序列:n);printf( 递归算法:);PostOrder(b);printf(n);printf( 非递归算法1:);PostOrder1(b);printf(n);printf( 非递归算法2:);PostOrder2(b);printf(n); void PreOrder(BTNode *b) /*先序遍历的递归算法*/if (b!=NULL) printf(%c ,b-data);/*访问根结点*/PreOrder(b-lchild);/*递归访问左子树*/PreOrder(b-rchild);/*递归访问右子树*/void PreOrder1(BTNode *b) /*先序遍历的非递归算法1*/BTNode *p;struct BTNode *pt;int tag; StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/*栈不空时循环*/if (Sttop.tag=1)/*不能直接访问的情况*/p=Sttop.pt;top-;if (p!=NULL)top+;/*右孩子进栈*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子进栈*/Sttop.pt=p-lchild;Sttop.tag=1;top+;/*根结点进栈*/Sttop.pt=p;Sttop.tag=0;if (Sttop.tag=0)/*直接访问的情况*/printf(%c ,Sttop.pt-data);top-; void PreOrder2(BTNode *b) /*先序遍历的非递归算法2*/BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) top+;/*根结点入栈*/ Sttop=b; while (top-1)/*栈不为空时循环*/ p=Sttop;/*退栈并访问该结点*/ top-; printf(%c ,p-data); if (p-rchild!=NULL)/*右孩子入栈*/ top+; Sttop=p-rchild; if (p-lchild!=NULL)/*左孩子入栈*/ top+; Sttop=p-lchild;printf(n);void InOrder(BTNode *b) /*中序遍历的递归算法*/if (b!=NULL) InOrder(b-lchild);/*递归访问左子树*/printf(%c ,b-data);/*访问根结点*/InOrder(b-rchild);/*递归访问右子树*/void InOrder1(BTNode *b) /*中序遍历的非递归算法1*/BTNode *p;struct BTNode *pt;int tag; StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/*栈不空时循环*/if (Sttop.tag=1)/*不能直接访问的情况*/p=Sttop.pt;top-;if (p!=NULL)top+;/*右孩子进栈*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*根结点进栈*/Sttop.pt=p;Sttop.tag=0;top+;/*左孩子进栈*/Sttop.pt=p-lchild;Sttop.tag=1;if (Sttop.tag=0)/*直接访问的情况*/printf(%c ,Sttop.pt-data);top-;void InOrder2(BTNode *b) /*中序遍历的非递归算法2*/BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top-1 | p!=NULL)while (p!=NULL)top+;Sttop=p;p=p-lchild;if (top-1)p=Sttop;top-;printf(%c ,p-data);p=p-rchild;printf(n);void PostOrder(BTNode *b) /*后序遍历的递归算法*/if (b!=NULL) PostOrder(b-lchild);/*递归访问左子树*/PostOrder(b-rchild);/*递归访问右子树*/printf(%c ,b-data);/*访问根结点*/void PostOrder1(BTNode *b) /*后序遍历的非递归算法1*/BTNode *p;struct BTNode *pt;int tag; StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/*栈不空时循环*/if (Sttop.tag=1)/*不能直接访问的情况*/p=Sttop.pt;top-;if (p!=NULL)top+;/*根结点进栈*/Sttop.pt=p;Sttop.tag=0;top+;/*右孩子进栈*/Sttop.pt=p-rchild;Sttop.tag=1;top+;/*左孩子进栈*/Sttop.pt=p-lchild;Sttop.tag=1;if (Sttop.tag=0)/*直接访问的情况*/printf(%c ,Sttop.pt-data);top-;void PostOrder2(BTNode *b) /*后序遍历的非递归算法2*/BTNode *StMaxSize;BTNode *p;int flag,top=-1;/*栈指针置初值*/if (b!=NULL)dowhile (b!=NULL)/*将t的所有左结点入栈*/top+;Sttop=b;b=b-lchild;p=NULL;/*p指向当前结点的前一个已访问的结点*/flag=1;/*设置b的访问标记为已访问过*/while (top!=-1 & flag)b=Sttop;/*取出当前的栈顶元素*/if (b-rchild=p)/*右子树不存在或已被访问,访问之*/printf(%c ,b-data);/*访问*b结点*/top-;p=b;/*p指向则被访问的结点*/elseb=b-rchild;/*t指向右子树*/flag=0;/*设置未被访问的标记*/ while (top!=-1);printf(n); void TravLevel(BTNode *b)BTNode *QuMaxSize;/*定义循环队列*/int front,rear;/*定义队首和队尾指针*/front=rear=0;/*置队列为空队列*/ if (b!=NULL) printf(%c ,b-data); rear+;/*结点指针进入队列*/Qurear=b; while (rear!=front)/*队列不为空*/ front=(front+1)%MaxSize;b=Qufront;/*队头出队列*/if (b-lchild!=NULL)/*输出左孩子,并入队列*/printf(%c ,b-lchild-data);rear=(rear+1)%MaxSize;Qurear=b-lchild;if (b-rchild!=NULL)/*输出右孩子,并入队列*/printf(%c ,b-rchild-data);rear=(rear+1)%MaxSize;Qurear=b-rchild; printf(n);void CreateBTNode(BTNode *&b,char *str)/*由str串创建二叉链*/BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!=0)/*str未扫描完时循环*/ switch(ch) case (:top+;Sttop=p;k=1; break;/*为左结点*/case ):top-;break;case ,:k=2; break; /*为右结点*/default:p=(BTNode *)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /*p指向二叉树的根结点*/b=p;else /*已建立二叉树根结点*/switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)/*以括号表示法输出二叉树*/if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();4.运行结果清单二叉树b：A（B(D,E(H(J,K(L,M(,N),C(F,G(,I)）层次遍历序列：A B C D E F G H I J K L M N先序遍历序列： 递归算法：A B D E H J K L M N C F G I 非递归算法1：A B D E