数据结构实验------二叉树操作2008-12-04 19:07按层次输入，这样可以根据实际需要建立树型，更为实用。但我的程序仍存在一个问题，就是遍历（2）：输出为空的孩子时都会多输出两个空孩子。不知道怎么改。
//二叉树结点类型为字符型的情况
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define null 0
#define MaxSize 1024
typedef struct tree
{ /*声明树的结构*/
struct tree *left; /*存放左子树的指针*/
struct tree *right; /*存放又子树的指针*/
char data; /*存放节点的内容*/
} treenode, * b_tree; /*声明二叉树的链表*/
b_tree Q[MaxSize];
/*建立二叉树，按完全二叉树的层次遍历序列输入*/
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[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->left=s;
else
Q[front]->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 ;
/*定义队列结点类型*/
typedef struct QueueNode
{
ElemType data;
struct QueueNode *next;
} QueueNode;
/*定义队列*/
typedef struct linkQueue
{
QueueNode * front;
QueueNode * rear;
}linkQueue;
/*初始化队列*/
void initQueue(linkQueue * q)
{
q->front=q->rear =null; //----无头结点
}
/*判断队列是否为空*/
int QueueEmpty(linkQueue * Q)
{
return (Q->front==null)&&(Q->rear==null);
/*实际上只须判断队头指针是否为空即可*/
}
/*入队操作*/
void EnQueue(linkQueue *Q,ElemType x)
{ /*将元素x插入链队列尾部*/
QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode)); /*申请新结点*/
p->data=x; p->next=null;
if(QueueEmpty(Q)) /*将x插入空队列*/ //----无头结点
Q->front=Q->rear=p;
else
{ /*x插入非空队列的尾*/
Q->rear->next=p; /*p链到原队尾结点后*/
Q->rear=p; /*队尾指针指向新的尾*/
}
}
/*出队操作*/
ElemType DeQueue (linkQueue *Q)
{
ElemType x;
QueueNode *p;
if(QueueEmpty(Q))
{
printf("Queue underflow");/*下溢*/
exit(1) ;
}
p=Q->front; /*指向对头结点*/
x=p->data; /*保存对头结点的数据*/
Q->front=p->next; /*将对头结点从链上摘下*/
if(Q->rear==p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/
Q->rear=NULL;
free(p); /*释放被删队头结点*/
return x; /*返回原队头数据*/
}
void visit(b_tree p)
{
printf("%3c",p->data);
}
void breadthFirst2(b_tree root)
{
b_tree p,tmp;
linkQueue * q;
tmp=(treenode *)malloc(sizeof(treenode));
q=(linkQueue *)malloc(sizeof(linkQueue));
tmp->data='?';
initQueue(q);
p=root;
if(p!=null)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->data!='?')
{
if(p->left!=null)
EnQueue(q,p->left);
else
EnQueue(q,tmp);
if(p->right!=null)
EnQueue(q,p->right);
else
EnQueue(q,tmp);
}
}
}
}
void breadthFirst(b_tree root)
{
b_tree p;
linkQueue * q;
q=(linkQueue *)malloc(sizeof(linkQueue));
initQueue(q);
p=root;
if(p!=null)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->left!=null)
EnQueue(q,p->left);
if(p->right!=null)
EnQueue(q,p->right);
}
}
}
int main()
{
char nodelist[MaxSize];
int len,flag;
char cmd;
b_tree root;
printf("\n\n----------------------------------------------------\n");
printf("\n****欢迎测试和修正本程序！本程序用以研究二叉树。****\n");
printf("\n----------------------------------------------------\n\n");
do
{
printf("\n\n 请选择你要执行的操作:\n\n");
printf(" c,C......创建一棵二叉排序树\n");
printf(" a,A......结束本程序\n\n");
flag=0;
do
{
if(flag!=0)
printf("选择操作错误！请重新选择！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
printf("请输入那你所要创建的二叉树的结点的值,以‘？’结束）：\n");
getchar();
root=createbtree();
do
{
flag=0;
printf("\n\n 请选择你要对这棵二叉树所做的操作:\n\n");
printf(" x,X......先序遍历这棵二叉树\n");
printf(" z,Z......中序遍历这棵二叉树\n");
printf(" h,H......后序遍历这棵二叉树\n");
printf(" b,B......层次遍历这棵二叉树\n");
printf(" d,D......求这棵二叉树的高度\n");
printf(" y,Y......求这棵二叉树的叶子总数\n");
printf(" j,J......输出这棵二叉树的叶子结点\n");
printf(" q,Q......结束对这棵二叉树的操作\n\n");
do
{
if(flag!=0)
printf("选择操作错误！请重新选择！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='x'&&cmd!='X'&&cmd!='z'&&cmd!='Z'&&cmd!='h'&&cmd!='H'&&cmd!='b'&&cmd!='B'&&cmd!='d'&&cmd!='D'&&cmd!='y'&&cmd!='Y'&&cmd!='j'&&cmd!='J'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{
case 'x':
case 'X':
printf("\n先序遍历开始:\n");
preorder_btree(root);
printf("\n先序遍历结束\n\n");
break;
case 'z':
case 'Z':
printf("\n中序遍历开始:\n");
inorder_btree(root);
printf("\n中序遍历结束\n\n");
break;
case 'h':
case 'H':
printf("\n后序遍历开始:\n");
postorder_btree(root);
printf("\n后序遍历结束\n\n");
break;
case 'b':
case 'B':
printf("\n层次遍历开始:\n");
printf("遍历（1）：不输出为空的孩子\n");
breadthFirst(root);
printf("\n");
printf("遍历（2）：输出为空的孩子\n");
breadthFirst2(root);
printf("\n层次遍历结束\n\n");
break;
case 'd':
case 'D':
printf("\n这棵二叉树的高度：\n%d\n\n",treedepth(root));
break;
case 'y':
case 'Y':
count=0;
count=leafcount(root);
printf("\n这棵二叉树的叶子总数为:\n%d\n\n",count);
count=0;
break;
case 'j':
case 'J':
printf("\n这棵二叉树的叶子结点为：\n");
paintleaf(root);
printf("\n");
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='a'&&cmd!='A');
printf("\n\n----------------------------\n\n");
printf("****谢谢使用！欢迎指正！****\n\n");
printf("----------------------------\n\n");
printf("作者：Remainder 学号：07082107 时间：2008.11.23\n\n\n\n");
return 0;
}
/*（10
（8 5 3 34 23 73 15 34 56 32）。。。。。。结点数据整型时
6
1 2 3 4 5 6
4
a b c d
*/
上面是我写的程序，下面是我的空间，希望对你有用！
参考资料：http://hi.baidu.com/yy_christine
本回答被提问者采纳