二叉树的遍历图解例题,二叉树的先序,中序,后序遍历python

# include stdlib.h # include stdio.h # definemaxqsize 50 # define stack _ init _ size 50 # define true1/*状态代码预定义typedef char TElemType； typedefstructbitnode { telemtypedata； struct BiTNode *lchild，*rchild； //左右儿童的指针(}BiTNode，*BiTree； typedef struct BiTNode* QElemtype； typedef struct BiTNode* SElemtype； typedef struct{ QElemtype *base； int front，rear； }SqQueue； typedef struct { selemtypebase [ stack _ init _ size ]； int top； int stacksize； }SqStack； statusinitstack(sqstack*s ) { S-top=0； S-stacksize=STACK_INIT_SIZE； 返回确定； }selemtypegettop(sqstacks ) if ) s.top==0) return ERROR； else return S.base[S.top-1]； }statuspush(sqstack*s，SElemtype e ) { S-base[S-top ]=e； 返回确定； }selemtypepop(sqstack*s ) if ) s-top==0) return ERROR； S-top--； return S-base[S-top]； }statusstackempty(sqstacks ) { return S.top==0； }intgetstacksize(sqstacks ) { return S.top-1； }statusinitqueue(sqqueue*q ) q-base=) qelemtype* ) malloc ) sizeof ) qelemtype )； if (！ Q-base ) exit(overflow )； Q-front=Q-rear=0； 返回确定； }statusenqueue(sqqueue*q，QElemtype e ) if((q-rear1) %MAXQSIZE==Q-front )/ifthequeueueisfull/{ printf } 返回错误； } Q-base[Q-rear]=e； q-rear=(q-rear1) %MAXQSIZE； 返回确定； }statusdequeue(sqqueue*q，QElemtype *e ) if ) q-front==q-rear ) printf ) ' thequeueisempty！ n '； 返回错误； } *e=Q-base[Q-front]； q-front=(q-front1) %MAXQSIZE； 返回确定； }statustraversequeue(sqqueueq ) { int i； i=Q.front； 打印(theelementsinthequeueare : )； wile () I%maxqsize )！=Q.rear () printf ) ' %d '，Q.base[i]； I； }printf((n )； 返回确定； }statusqueueempty(sqqueueq ) { return q.rear==q.front； }statuscreatebitree_1(bitree*t，char ch[] () ) ) /遍历以创建节点，然后单击递归(自动填充) { static int i=-1； //静态变量I； if(ch[I]=='# ' ) *T=NULL； Elseif(ch[I]！=' ' () t=(bitnode* ) malloc (sizeof ) bitnode ) )； 为//T分配内存空间 if(T==NULL) exit(OVERFLOW); (*T)->data=ch[i]; CreateBiTree_1(&(*T)->lchild,ch); CreateBiTree_1(&(*T)->rchild,ch); } return OK;}Status PrintElement(TElemType e) //简单的打印元素函数{ printf("%c",e); return OK;}/*先序遍历，使用递归*/void PreOrderTraverse(BiTree T,Status (*visit)(TElemType e)) { if(T==NULL) return; visit(T->data); PreOrderTraverse(T->lchild,visit); PreOrderTraverse(T->rchild,visit); }/*非递归中序遍历方法1 算法6.1 P130 */Status InOrderTraverse_1(BiTree T,Status (*visit)(TElemType e)){ SqStack S; BiTree p; InitStack(&S); //初始化栈 Push(&S,T); while(!StackEmpty(S)) //栈非空 { while(p=GetTop(S)) Push(&S,p->lchild); p=Pop(&S); if(!StackEmpty(S)) { p=Pop(&S); if(!visit(p->data)) return ERROR; Push(&S,p->rchild); } }}/*非递归中序遍历方法2 算法6.2 P131*/Status InOrderTraverse_2(BiTree T,Status(*visit)(TElemType e)){ SqStack S; BiTree p; InitStack(&S); p=T; while(p||!StackEmpty(S)) { if(p) { Push(&S,p); p=p->lchild; } //左子树全部进栈 else { p=Pop(&S); if(!visit(p->data)) return ERROR; p=p->rchild; } } return OK;}/*递归后序遍历*/Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)){ if(T==NULL) return ERROR; PostOrderTraverse(T->lchild,visit); /*先左后右*/ PostOrderTraverse(T->rchild,visit); visit(T->data);}/* */int NodeCount(BiTree T){if(T==NULL) return FALSE;else return NodeCount(T->lchild)+ NodeCount(T->rchild)+1;}/*递归后序遍历（3）在上述二叉树的基础上，后序遍历，求解二叉树深度的算法*/int Depth(BiTree T){int m,n;if(T==NULL) return FALSE;else {m=Depth(T->lchild);n=Depth(T->rchild);if(m>n) return (m+1);else return(n+1);}}/*（2）在上述二叉树的基础上，实现先序遍历，统计叶子节点个数的算法*///后序int CountLeaf(BiTree &T){ // int cright,cleft; if (T==NULL) return 0; if ((T->lchild==NULL)&&(T->rchild==NULL)) return 1; // 对叶子结点计数/* else { cleft=CountLeaf(T->lchild); cright=CountLeaf(T->rchild); return (cleft+cright); } */ return CountLeaf(T->lchild)+CountLeaf(T->rchild); } // CountLeaf/* void leaf(BiTree T){//递归统计叶子节点的数目 int count; if(T){ if(T->lchild==NULL&&T->rchild==NULL) count++; leaf(T->lchild); leaf(T->rchild); }}*///先序/*int CountLeaf(BiTree T,int count){ if(T){ if ((T->lchild==NULL)&& (T->rchild==NULL)) count++; // 对叶子结点计数 count=CountLeaf( T->lchild,count); count =CountLeaf( T->rchild,count); }} // CountLeaf //后序int Countleaf(BiTree T){ if(T==NULL) return 0; if ((T->lchild==NULL)&& (T->rchild==NULL)) return 1; // 对叶子结点计数 else return Countleaf(T->lchild)+ Countleaf(T->rchild);}// CountLeaf*/void main(){ BiTree T; char ch[]="ABDF###E##C##"; //测试数据 先序序列 CreateBiTree_1(&T,ch); //二选一 //CreateBiTree_2(&T); //此为符合实验要求函数 //NodeCount(T);//Depth(T); printf("二叉树结点的个数是%d个:n",NodeCount(T)); printf("二叉树叶子结点的个数是%d个:n",CountLeaf(T));// printf("二叉树叶子结点的个数是%d个:n",CountLeaf(T,0)); printf("二叉树的深度是%d:n",Depth(T)); printf("后序遍历:n"); PostOrderTraverse(T,PrintElement); printf("n先序遍历:n"); PreOrderTraverse(T,PrintElement); printf("n非递归中序遍历方法1:n"); InOrderTraverse_1(T,PrintElement); printf("n非递归中序遍历方法2:n"); InOrderTraverse_2(T,PrintElement); printf("n");}