二叉树各种遍历方法实现

#include"Head.h" /******************************************/ //树的算法实现 //创建二叉树 BiTree createBTpre() { BiTree T; char ch; scanf_s("%c" , &ch); if(ch=='#') T=NULL; else { if(!(T=( BiTree )malloc(sizeof(BiTNode)))) return ERROR; T->data=ch; T->lchild=createBTpre(); T->rchild=createBTpre(); } return T; } int createTree(BiTree *T) { char ch; scanf_s("%c" , &ch); if(ch=='#') *T=NULL; else { if(!(*T=( BiTree )malloc(sizeof(BiTNode)))) return ERROR; (*T)->data=ch; createTree(&(*T)->lchild); createTree(&(*T)->rchild); } return OK; } //先序 void printfirst(BiTree T) { if(!T) { return; } printf("%c\t",T->data); printfirst(T->lchild); printfirst(T->rchild); }//递归 int FirstTraverse(BiTree T) { SqStack S; BiTree p; InitStack(&S); p=T; while(p||!StackEmpty(S)) { if(p) { Push(&S,p); printf("%c\t",p->data); p=p->lchild; } else { Pop(&S,&p); p=p->rchild; } } return OK; } //中序 void printmiddle(BiTree T) { if(!T) { return; } printmiddle(T->lchild); printf("%c\t",T->data); printmiddle(T->rchild); }//递归 int MidTraverse1(BiTree T) { SqStack S; BiTree p; InitStack(&S); Push(&S,T); while(!StackEmpty(S)) { while(GetTop(S,&p)&&p) { Push(&S,p->lchild); } Pop(&S,&p); if(!StackEmpty(S)) { Pop(&S,&p); printf("%c\t",p->data); Push(&S,p->rchild); } } return OK; } int MidTraverse2(BiTree T) { SqStack S; BiTree p; InitStack(&S); p=T; while(p||!StackEmpty(S)) { if(p) { Push(&S,p); p=p->lchild; } else { Pop(&S,&p); printf("%c\t",p->data); p=p->rchild; } } return OK; } //后序 void printlast(BiTree T) { if(!T) { return; } printlast(T->lchild); printlast(T->rchild); printf("%c\t",T->data); } int LastTraverse(BiTree T)//@@@@@ { SqStack S; BiTree p,temp; BiTree pre = NULL;//pre表示最近一次访问的结点 InitStack(&S); p=T; while(p || !StackEmpty(S)) { //沿着左孩子方向走到最左下 。 while(p) { Push(&S,p); p = p->lchild; } //get the top element of the stack GetTop(S,&p); //如果p没有右孩子或者其右孩子刚刚被访问过 if(p->rchild == NULL || p->rchild == pre) { //visit this element and then pop it printf("%c\t",p->data); Pop(&S,&temp); pre = p; p = NULL; } else { p = p->rchild; } } return OK; } //level int LevelTraverse(BiTree T) { SqQueue Q; BiTree p; Sq_InitQueue(&Q); p=T; Sq_EnQueue(&Q,p); while(!Sq_QueueEmpty(Q)) { Sq_DeQueue(&Q,&p); printf("%c\t",p->data); printf("%d\t%d\n",p->lchild,p->rchild); if(p->lchild) { Sq_EnQueue(&Q,p->lchild); } if(p->rchild) { Sq_EnQueue(&Q,p->rchild); } } return OK; } //计算二叉树中叶子结点的个数 int fleafsum(BiTree T) { int fsum=0; if(T) { if(!T->lchild&&!T->rchild) { fsum++; printf("FSUM:%c\n",T->data); } fsum+=fleafsum(T->lchild); fsum+=fleafsum(T->rchild); } return fsum; } int mleafsum(BiTree T) { int msum=0; if(T) { msum+=mleafsum(T->lchild); if(!T->lchild&&!T->rchild) { msum++; printf("MSUM:%c\n",T->data); } msum+=mleafsum(T->rchild); } return msum; } int lleafsum(BiTree T) { int lsum=0; if(T) { lsum+=lleafsum(T->lchild); lsum+=lleafsum(T->rchild); if(!T->lchild&&!T->rchild) { lsum++; printf("LSUM:%c\n",T->data); } } return lsum; } int leafsum(BiTree T) { int sum=0; SqStack S; BiTree p; InitStack(&S); p=T; while(p||!StackEmpty(S)) { if(p) { Push(&S,p); p=p->lchild; } else { Pop(&S,&p); if(!p->lchild&&!p->rchild) sum++; p=p->rchild; } } return sum; } int TreeDeep(BiTree T)//递归算法 { int nl, nr; if( T == NULL ) return 0; else { nl = TreeDeep(T->lchild) + 1; nr = TreeDeep(T->rchild) + 1; return (nl > nr ? nl : nr); } } int DepthTree(BiTree T) //非递归 { BiTree p; int depth, max; SqStack S; InitStack(&S); p=T; depth=max=0; while(p||!StackEmpty(S)) { if(p) { Push(&S,p); if(p->lchild||p->rchild) depth++; p=p->lchild; if(max<depth) max=depth; } else { Pop(&S,&p); p=p->rchild; } } return max+1; } int WQErChaTree(BiTree T) { SqQueue Q; BiTree p,pre; Sq_InitQueue(&Q); pre=p=T; Sq_EnQueue(&Q,p); if(T==NULL) return ERROR; while(!Sq_QueueEmpty(Q)) { Sq_DeQueue(&Q,&p); if(p) { printf("%c\t",p->data); printf("%d\t%d\n",p->lchild,p->rchild); } if(pre==NULL&&p!=NULL) { printf("ERROR\n"); return FALSE; } if(p) { Sq_EnQueue(&Q,p->lchild); Sq_EnQueue(&Q,p->rchild); } pre=p; } printf("TRUE\n"); return TRUE; }