#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct TNode{
char data;
struct TNode*lchild,*rchild;
}TNode,*Tree;
Tree Creat( )//按先序序列建立二叉树
{
Tree T;
char ch=getchar();
if(ch=='#')
T=NULL;
else
{
T=(TNode*)malloc(sizeof(TNode));
T->data=ch;
T->lchild=Creat();
T->rchild=Creat();
}
return T;
}
void PreOrder(Tree T)//先序遍历————递归
{
TNode *p=T;
if (p != NULL)
{
printf(" %c",p->data);
PreOrder(p->lchild ) ;
Preorder(p->rchild ) ;
}
}
void Middle(Tree T)//中序遍历——递归
{
TNode *p=T;
if (p != NULL)
{
Middle( p-> lchild ) ;
printf(" %c", p ->data);
Middle(p-> rchild ) ;
}
}
void PostOrder(Tree T)//后序遍历——递归
{
TNode *p=T;
if (p != NULL){
PostOrder( p-> lchild ) ;
PostOrder( p-> rchild ) ;
printf(" %c", p ->data);
}
}
int Leaf(Tree T)//叶子结点个数
{
TNode *p=T;
if(p != NULL)
{
if((p->lchild==NULL)&&(p->rchild==NULL))
return 1;
else
return(Leaf(p->lchild)+Leaf(p->rchild));
}
else
return 0;
}
int Depth(Tree T)//树的深度
{
TNode *p=T;
int l,r;
if(!p)
return 0;
else
{
l=Depth(p->lchild);
r=Depth(p->rchild);
if(l>r)
return l+1;
else
returnr+1;
}
}
void Change(Tree T)//结点交换
{
TNode *p=T;
if(p!=NULL)
{
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
Change(T->lchild);
Change(T->rchild);
}
}
void ShowMenu()
{
printf("\t\t\t****二叉树算法**** \n");
printf("\t\t\t~~~~~~~~~~~~~~~~ \n");
printf("\t\t\t#1. 先序遍历 #\n");
printf("\t\t\t#2. 中序遍历 #\n");
printf("\t\t\t#3. 后序遍历 #\n");
printf("\t\t\t#4. 叶子个数 #\n");
printf("\t\t\t#5. 二叉树深度 #\n");
printf("\t\t\t#6. 结点交换 #\n");
printf("\t\t\t#0. 退出程序 #\n");
printf("\t\t\t~~~~~~~~~~~~~~~~\n");
}
int main()
{
Tree T;
int t, l, d ;
printf("\t\t\t****创建二叉树****\n");
printf("◤请输入树的各元素，用#表示空结点：\n");
T=Creat();
while(1)
{
ShowMenu();
printf("◤请您选择(0-6):");
scanf("%d",&t);
switch(t)
{
case1: printf(" ◎先序遍历:");PreOrder(T);printf("\n"); break;
case 2: printf(" ◎中序遍历:");Middle(T);printf("\n"); break;
case3: printf(" ◎后序遍历:");PostOrder(T); printf("\n"); break;
case4: printf(" ◎叶子结点个数:");l=Leaf(T);printf(" %d 个\n",l); break;
case5: printf(" ◎二叉树深度:");d=Depth(T);printf(" %d\n",d); break;
case6: printf(" █各结点已交换█");Change(T);printf("\n",d); break;
case0: printf("\t\t******谢谢使用,再见!******\n");return 0;break;
default: printf("※输入出错!!!请重输：\n");
}
}