树和二叉树.doc

#include #include #define OK 1#define ERROR 0#define OVERFLOW -2int i=0,j=0;#define TElemType char /二叉链表结点类型typedef struct BiTNodeTElemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree CreateBiTree(BiTree T)TElemType ch;if (ch=getchar()= )T=NULL;elseif (!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);T-data=ch;T-lchild=CreateBiTree(T-lchild);T-rchild=CreateBiTree(T-rchild);return T;void InOrderTraverse(BiTree T) /中序递归遍历二叉树if(T)InOrderTraverse(T-lchild);printf(%c,T-data);InOrderTraverse(T-rchild);/非递归中序遍历typedef struct /顺序栈类型定义 BiTree *base;BiTree *top;int stacksize;SqStack;void InitStack(SqStack &S) /栈初始化S.base=(BiTree *)malloc(sizeof(BiTree);if(S.base=NULL)exit(0); S.top=S.base;S.stacksize=100;int PushStack(SqStack &S,BiTree p) /入栈*S.top+=p;return 1;BiTree PopStack(SqStack &S,BiTree &p) /出栈if(S.top=S.base)return p;p=*-S.top;return p;void InOrderTraverse2(BiTree T) /中序非递归遍历SqStack S;InitStack(S);BiTree P=T;while(P|(S.base!=S.top)if(P)PushStack(S,P);P=P-lchild;elsePopStack(S,P);printf(%c,P-data); P=P-rchild;/-层次遍历-typedef struct QNodeBiTree data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;void InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(0);Q.front-next=NULL;BiTree EnQueue(LinkQueue &Q,BiTree e) /入队QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return e;BiTree DeQueue(LinkQueue &Q) /出队QueuePtr p;BiTree e;p=(QueuePtr)malloc(sizeof(QNode);p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return e;void LevelOrderTraverse(BiTree p) /层次遍历LinkQueue q;q.rear=q.front=(QueuePtr)malloc(sizeof(QNode);InitQueue(q);EnQueue(q,p);BiTree T;while(q.front!=q.rear)T=DeQueue(q);printf(%c,T-data);if(T-lchild)EnQueue(q,T-lchild);if(T-rchild)EnQueue(q,T-rchild);printf(n);/-int Depth(BiTree T) /求二叉树高度if(T=NULL)return 0;elseint deep1=Depth(T-lchild);int deep2=Depth(T-rchild);if(deep1=deep2)return deep1+1;elsereturn deep2+1;void Node(BiTree T) /求结点个数if(T)i+;Node(T-lchild);Node(T-rchild);void Leaf(BiTree T) /求叶子个数if(T)if(T-lchild=NULL&T-rchild=NULL)j+;Leaf(T-lchild);Leaf(T-rchild);void Exchange(BiTree T) /交换左右子树 BiTree temp; if(T) Exchange(T-lchild); Exchange(T-rchild); temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; void main()int c;BiTree T;T=NULL;for(;)printf(n主菜单:n);printf(1:建立一棵二叉树n);printf(2:中序递归遍历二叉树n);printf(3:中序非递归遍历二叉树n);printf(4:层次遍历二叉树n);printf(5:求二叉树的高度n);printf(6:求二叉树的结点个数n);printf(7:求二叉树的叶子个数n);printf(8:交换二叉树每个结点的左子树和右子树n); printf(请选择相应的操作:n); scanf(%d,&c);getchar();switch(c)case 1:printf(请输入字符数据:n); T=CreateBiTree(T);printf(二叉树建立完毕n);break;case 2:printf(中序递归遍历:n); InOrderTraverse(T); printf(n);break; case 3:printf(中序非递归遍历:n); InOrderTraverse2(T); printf(n); break; case 4:printf(层次遍历:n); LevelOrderTraverse(T);break;case 5:Depth(T); printf(二叉树的高度为:%d,Depth(T); printf(n);break