二叉树子系统.doc

#include#include #define TREEMAX 100typedef struct BT/ 定义二叉树结构体 char data; struct BT* lchild; struct BT* rchild;BT;BT *CreateTree();void ShowTree(BT *T);void Preorder(BT *T);void Postorder(BT *T);void Levelorder(BT *T);void Inorder(BT *T);void Leafnum(BT *T);void Nodenum(BT *T);int TreeDepth(BT *T);int count=0;/ 定义计算结点个数的变量void main() BT *T=NULL; char ch1,ch2,a; ch1=y; while(ch1=y|ch1=Y) printf(n);printf(ntt 二叉树子系统);printf(ntt*);printf(ntt* 1-建 二 叉 树 *);printf(ntt* 2-凹 入 显 示 *);printf(ntt* 3-先 序 遍 历 *);printf(ntt* 4-中 序 遍 历 *);printf(ntt* 5-后 序 遍 历 *);printf(ntt* 6-层 次 遍 历 *);printf(ntt* 7-求 叶 子 数 *);printf(ntt* 8-求 结 点 数 *);printf(ntt* 9-求 树 深 度 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(ntt 请选择菜单号(0-9)：);scanf(%c,&ch2);getchar();printf(n);switch(ch2) case 1:printf(ntt请按先序序列输入二叉树的结点：n);printf(ntt说明:输入结点(0表示后继结点为空)后按回车.n);printf(ntt请输入根结点：);T=CreateTree();printf(ntt二叉树成功建立!n);break; case2:ShowTree(T);break; case3:printf(ntt该二叉树的先序遍历序列为：);Preorder(T);break; case4:printf(ntt该二叉树的中序遍历序列为：);Inorder(T);break; case5:printf(ntt该二叉树的后序遍历序列为：);Postorder(T);break; case6:printf(ntt该二叉树的层次遍历序列为：);Levelorder(T);break; case7:count=0;Leafnum(T);printf(ntt该二叉树有%d个叶子。n,count);break; case8:count=0;Nodenum(T);printf(ntt该二叉树总共有%d个结点。n,count);break; case9:printf(ntt该树的深度是：%d,TreeDepth(T);break; case0:ch1=n;break; default:printf(ntt*请注意：输入有误!*);if(ch2!=0) printf(nntt按回车键继续，按任意键返回主菜单!n); a=getchar(); if(a!=xA) getchar();ch1=n; BT *CreateTree() / 建立二叉树 BT *t; char x; scanf(%c,&x); getchar(); if(x=0)t=NULL; else t=(BT *)malloc(sizeof(BT);t-data=x;printf(ntt请输入%c结点的左子结点：,t-data);t-lchild=CreateTree();printf(ntt请输入%c结点的右子结点：,t-data);t-rchild=CreateTree(); return t;void Preorder(BT *T) / 先序遍历 if(T) printf(%3c,T-data);Preorder(T-lchild);Preorder(T-rchild); void Inorder(BT *T) / 中序遍历 if(T) Inorder(T-lchild);printf(%3c,T-data);Inorder(T-rchild); void Postorder(BT *T) / 后序遍历 if(T) Postorder(T-lchild);Postorder(T-rchild);printf(%3c,T-data); void Levelorder(BT *T) / 层次遍历 int i,j; BT *q100,*p; p=T; if(p!=NULL) i=1;qi=p; j=2; while(i!=j) p=qi;printf(%3c,p-data);if(p-lchild!=NULL) qj=p-lchild;j+; if(p-rchild!=NULL) qj=p-rchild; j+;i+; void Leafnum(BT *T) / 求叶子数 if(T) if(T-lchild=NULL&T-rchild=NULL) count+;Leafnum(T-lchild);Leafnum(T-rchild); void Nodenum(BT *T) / 求结点数 if(T) count+;Nodenum(T-lchild);Nodenum(T-rchild); int TreeDepth(BT *T) / 求树深度 int ldep,rdep; if(T=NULL)return 0; else ldep=TreeDepth(T-lchild);rdep=TreeDepth(T-rchild);if(ldeprdep) return ldep+1;else return rdep+1; void ShowTree(BT *T) / 凹入法显示二叉树 BT *stackTREEMAX,*p; int levelTREEMAX2,top,n,i,width=4; if(T!=NULL) printf(ntt凹入表示法：ntt);top=1;stacktop=T;leveltop0=width;while(top0) p=stacktop; n=leveltop0; for(i=1;idata); for(i=n+1;irchil