//二叉树结点类型为字符型的情况
#include
#include
#include
#define null 0
#define MaxSize 1024
typedef struct tree
{ /*声明树的结构*/
struct tree *left;
/*存放左子树的指针*/
st...ruct tree *right; /*存放右子树的指针*/
char data;
/*存放节点的内容*/
} treenode, * b_tree;
/*声明二叉树的链表*/
b_tree Q;
/*建立二叉树，按完全二叉树的层次遍历序列输入*/
b_tree createbtree()
{
char ch;
int front,rear;
b_tree root,s;
root=NULL;
front=1;rear=0;
ch=getchar();
getchar();
while(ch!='?')
{
s=NULL;
if(ch!='.')
{
s=(b_tree)malloc(sizeof(treenode));
s->data=ch;
s->left=NULL;
s->right=NULL;
}
rear++;
Q=s;
if(rear==1)
root=s;
else
{
if(s&&Q)
if(rear%2==0)
Q->left=s;
else
Q->right=s;
if(rear%2==1)
front++;
}
ch=getchar();
getchar();
}
return root;
}
/*先序遍历打印二叉排序树*/
void preorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null)
{
printf("%3c",p->data);
preorder_btree(p->left);
preorder_btree(p->right);
}
}
/* 中序遍历打印二叉排序树*/
void inorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null){
inorder_btree(p->left );
printf("%3c",p->data );
inorder_btree(p->right );
}
}
/*后序遍历打印二叉排序树*/
void postorder_btree(b_tree root)
{
b_tree p=root;
if(p!=null)
{
postorder_btree(p->left );
postorder_btree(p->right );
printf("%3c",p->data );
}
}
/*求树的高度*/
int treedepth(b_tree bt)
{
int hl,hr,max;
if(bt!=null)
{
hl=treedepth(bt->left);
hr=treedepth(bt->right);
max=(hl>hr)?hl:hr;
return (max+1);
}
else
return 0;
}
int count=0;
/*求叶子结点总数*/
int leafcount(b_tree bt)
{
if(bt!=null)
{
leafcount(bt->left);
leafcount(bt->right);
if(bt->left==null&&bt->right==null)
count++;
}
return count;
}
void paintleaf(b_tree bt)
{
if(bt!=null)
{
if(bt->left==null&&bt->right==null)
printf("%3c",bt->data);
paintleaf(bt->left);
paintleaf(bt->right);
}
}
typedef b_tree ElemType ;
int main()
{
char nodelist;
int len,flag;
char cmd;
b_tree root;
do
{
printf(" 输入c......选择创建一棵二叉排序树\n");
printf(" 输入a......将结束本程序\n\n");
flag=0;
do
{
if(flag!=0)
printf("选择操作错误！请重新选择！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='c'&&cmd!='a');
if(cmd=='c')
{
printf("请输入那你所要创建的二叉树的结点的值,以'？'结束）：\n");
getchar();
root=createbtree();
do
{
flag=0;
printf("\n\n 请选择你要对这棵二叉树所做的操作:\n\n");
printf(" x......先序遍历\n");
printf(" z......中序遍历\n");
printf(" h......后序遍历\n");
printf(" b......层次遍历\n");
printf(" d......求二叉树的深度\n");
printf(" y......求叶子总数并输出各叶子结点\n");
printf(" q......结束操作\n\n");
do
{
if(flag!=0)
printf("选择操作错误！请重新选择！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='x'&&cmd!='z'&&cmd!='h'&&cmd!='b'&&cmd!='d'&&cmd!='y'&&cmd!='j'&&cmd!='q');
switch(cmd)
{
case 'x':
printf("\n先序遍历开始:\n");
preorder_btree(root);
printf("\n先序遍历结束\n\n");
break;
case 'z':
printf("\n中序遍历开始:\n");
inorder_btree(root);
printf("\n中序遍历结束\n\n");
break;
case 'h':
printf("\n后序遍历开始:\n");
postorder_btree(root);
printf("\n后序遍历结束\n\n");
break;
case 'd':
printf("\n这棵二叉树的高度：\n%d\n\n",treedepth(root));
break;
case 'y':
printf("\n这棵二叉树的叶子结点为：\n");
paintleaf(root);
printf("\n");
count=0;
count=leafcount(root);
printf("\n这棵二叉树的叶子总数为:\n%d\n\n",count);
count=0;
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='a'&&cmd!='A');
printf("****谢谢使用！欢迎指正！****\n\n");
return 0;
}