二叉树.docx

二叉树#include #include typedef char ElemType;typedef char status;typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild;BiTNode;void Visit(BiTNode *p)printf(%c ,p-data);/* 先根遍历 */void preorder(BiTNode *bt) if(bt!=NULL) Visit(bt); preorder(bt-lchild); preorder(bt-rchild); /* 中根遍历 */void inorder(BiTNode *bt) if(bt!=NULL) inorder(bt-lchild); printf(%c ,bt-data); inorder(bt-rchild); /* 后根遍历 */void postorder(BiTNode *bt) if(bt!=NULL) postorder(bt-lchild); postorder(bt-rchild); printf(%c ,bt-data); /* 非递归算法的先根遍历（后进先出，用了栈的思想） */void preorder_fdg(BiTNode *bt) int i=0;BiTNode *p,*s20;p=bt;dowhile(p!=NULL)Visit(p);if(p-rchild!=NULL)si+=p-rchild;p=p-lchild;if(i0)p=s-i;while(i0|p!=NULL);/* 非递归算法的中根遍历（后进先出，用了栈的思想） */void inorder_fdg(BiTNode *bt) int i=0; BiTNode *p,*s20; p=bt; do while(p!=NULL) si+=p; p=p-lchild; if(i0) p=s-i; printf(%c ,p-data); p=p-rchild; while(i0|p!=NULL);/* 用队列实现层次遍历 */void lev_traverse(BiTNode* T) BiTNode *q100,*p; int head,tail; q0=T;head=0;tail=1; while(headdata); if(p-lchild!=NULL) qtail+=p-lchild; if(p-rchild!=NULL) qtail+=p-rchild; /* 利用先根序列建立二叉树，空的子树也要输入，用空格表示 */ BiTNode *crt_bt_pre() char ch; BiTNode *bt; scanf(%c,&ch); if(ch= ) bt=NULL; else bt=(BiTNode *)malloc(sizeof(BiTNode); bt-data=ch; bt-lchild=crt_bt_pre(); bt-rchild=crt_bt_pre(); return(bt);/* 二叉树的释放*/void freetree(BiTNode *bt) if(bt!=NULL) freetree(bt-lchild); freetree(bt-rchild); free(bt); bt=NULL; int main() int num; BiTNode* T; printf(请输入一个先序表示的二叉树：n); T = crt_bt_pre(); printf(* * * * * * * * * * * * * * * * *n); printf(* Function Menue *n); printf(* 1、先序遍历 *n); printf(* 2、中序遍历 *n); printf(* 3、后序便利 *n); printf(* 4、层序遍历 *n); printf(* 5、退出 *n); printf(* * * * * * * * * * * * * * * * *n); do printf(nnplease input num:n); scanf(%d,&num); switch(num) case 1: printf(nnPreOrder:n); preorder(T);printf(nnPreorder_fdg:n);preorder_fdg(T);break; case 2: printf(nnInOrder:n); inorder(T);printf(nninorder_fdg:n); inorder_fdg(T);break; case 3: printf(nnPostOrder:n); postorder(T);break; case 4: printf(nnlev_traverse:n); lev_traverse(T);break; case 5: break; while(num!=0); freetree(T); /* printf(nnplease input inorder:such as abc de g f n)