二叉树程序

#includestdlib.h#includeiostreamusingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineINITSIZE100#defineINCREMENT10#defineNULL0typedefintStatus;typedefcharTElemType;//二叉树定义typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//栈定义及操作typedefBiTreeSElemType;typedefstruct{SElemTypeelem[INITSIZE];inttop,base;}Stack;voidinitstack(Stack&S){S.top=0;S.base=0;}voidpush(Stack&S,SElemTypee){S.elem[S.top]=e;S.top++;}voidpop(Stack&S,SElemType&e){S.top--;e=S.elem[S.top];}StatusStackEmpty(StackS){return!(S.top-S.base);}//栈定义及操作//队列定义及操作typedefBiTreeQElemType;typedefstruct{QElemTypeelem[INITSIZE];intfront,rear;}Queue;voidinitqueue(Queue&Q){Q.front=0;Q.rear=0;}Statusenqueue(Queue&Q,QElemTypee){if((Q.rear+1)%INITSIZE==Q.front)returnERROR;Q.elem[Q.rear]=e;Q.rear=(Q.rear+1)%INITSIZE;returnOK;}Statusdequeue(Queue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.elem[Q.front];Q.front=(Q.front+1)%INITSIZE;returnOK;}StatusQueueEmpty(QueueQ){if(Q.front==Q.rear)returnOK;elsereturnERROR;}//队列定义及操作//先序建立二叉树递归算法Statuscreatebitree(BiTree&T){charch;cinch;if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;createbitree(T-lchild);createbitree(T-rchild);}returnOK;}//先序建立二叉树递归算法//遍历二叉树递归算法Statuspreordertraverse(BiTreeT){//先序遍历if(!T)returnOK;else{coutT-data;if(preordertraverse(T-lchild))if(preordertraverse(T-rchild))returnOK;}returnOK;}Statusinordertraverse(BiTreeT){//中序遍历if(!T)returnOK;else{if(inordertraverse(T-lchild)){coutT-data;if(inordertraverse(T-rchild))returnOK;}returnOK;}}Statuslastordertraverse(BiTreeT){//后序遍历if(!T)returnOK;else{if(lastordertraverse(T-lchild))if(lastordertraverse(T-rchild))coutT-data;}returnOK;}//遍历二叉树递归算法//遍历二叉树非递归算法Statuspretraverse(BiTreeT){//先序遍历StackS;BiTreep;if(!T)returnOK;initstack(S);p=T;while(p){coutp-data;push(S,p);p=p-lchild;}while(!StackEmpty(S)){pop(S,p);p=p-rchild;while(p){push(S,p);coutp-data;p=p-lchild;}}returnOK;}Statusintraverse(BiTreeT){//中序遍历StackS;BiTreep;if(!T)returnOK;initstack(S);p=T;while(p){push(S,p);p=p-lchild;}while(!StackEmpty(S)){pop(S,p);coutp-data;p=p-rchild;while(p){push(S,p);p=p-lchild;}}returnOK;}Statuslasttraverse(BiTreeT){//后序遍历StackS,F;BiTreep;if(!T)returnOK;initstack(S);initstack(F);p=T;while(p){push(F,p);push(S,p);p=p-rchild;}while(!StackEmpty(S)){pop(S,p);p=p-lchild;while(p){push(S,p);push(F,p);p=p-rchild;}}while(!StackEmpty(F)){pop(F,p);coutp-data;}returnOK;}Statusleveltraverse(BiTreeT){//层次遍历QueueQ;BiTreep;if(!T)returnOK;initqueue(Q);p=T;enqueue(Q,p);while(!QueueEmpty(Q)){dequeue(Q,p);coutp-data;if(p-lchild)enqueue(Q,p-lchild);if(p-rchild)enqueue(Q,p-rchild);}returnOK;}//遍历二叉树非递归算法//二叉树其他运算intlevel(BiTreeT){//求二叉树深度递归算法intl,h;if(!T)return0;l=level(T-lchild);h=level(T-rchild);if(l=h)returnl+1;elsereturnh+1;}intnum(BiTreeT){//求二叉树节点个数递归算法intln,rn;if(!T)return0;ln=num(T-lchild);rn=num(T-rchild);returnln+rn+1;}intleavenum(BiTreeT){//求叶子节点个数递归算法if(!T)return0;if(!T-lchild&&!T-rchild)return1;return(leavenum(T-lchild)+leavenum(T-rchild));}intleave(BiTreeT){//非递归先序遍历求叶子节点个数StackS;BiTreep;intleaf=0;if(!T)return(leaf);initstack(S);p=T;while(p){//coutp-data;if(!p-lchild&&!p-rchild)leaf++;push(S,p);p=p-lchild;}while(!StackEmpty(S)){pop(S,p);p=p-rchild;while(p){push(S,p);//coutp-data;if(!p-lchild&&!p-rchild)leaf++;p=p-lchild;}}return(leaf);}Statuscopytree(BiTreeT,BiTree&T1){//复制二叉树递归算法，将T复制为T1if(!T){T1=NULL;returnOK;}T1=new(BiTNode);T1-data=T-data;T1-lchild=NULL;T1-rchild=NULL;if(T-lchild)copytree(T-lchild,T1-lchild);if(T-rchild)copytree(T-rchild,T1-rchild);returnOK;}Statusclearbitree(BiTree&T){//清空二叉树QueueQ;StackS;BiTreep;if(!T)returnOK;initstack(S);initqueue(Q);p=T;enqueue(Q,p);while(!QueueEmpty(Q)){dequeue(Q,p);push(S,p);if(p-lchild)enqueue(Q,p-lchild);if(p-rchild)enqueue(Q,p-rchild);}while(!StackEmpty(S)){pop(S,p);free(p);}T=NULL;returnOK;}voidmain(){BiTreeT,T1;createbitree(T);cout先序遍历序列（递归）：;preordertraverse(T);cout'\n';cout中序遍历序列（递归）：;inordertraverse(T);cout'\n';cout后序遍历序列（递归）：;lastordertraverse(T);cout'\n';cout先序遍历序列（非递归）：;pretraverse(T);cout'\n';cout中序遍历序列（非递归）：;intraverse(T);cout'\n';cout后序遍历序列（非递归）：;lasttraverse(T);cout'\n';cout层次遍历序列（非递归）：;leveltraverse(T);cout'\n';cout二叉树深度：level(T);cout'\n';cout叶子个数（非递归）：leave(T);cout'\n';cout叶子个数（递归）：leavenum(T);cout'\n';cout节点个数：num(T)'\n';copytree(T,T1);cout复制二叉树先序遍历序列（非递归）：;pretraverse(T1);cout'\n';cout复制二叉树中序遍历序列（非递归）：;intraverse(T1);cout'\n';cout复制二叉树后序遍历序列（非递归）：;lasttraverse(T1);cout'\n';cout复制二叉树层次遍历序列（非递归）：;leveltraverse(T1);cout'\n';clearbitree(T1);cout清空复制二叉树：T1;cout'\n';}