C语言编写二叉树的建立与遍历
- 格式：doc
- 大小：30.50 KB
- 文档页数：3
C语言编写二叉树的建立与遍历 100分
标签：
回答：5 浏览：13346 提问时间：2006-06-23 13:19
1．对题目要有需求分析
在需求分析中，将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，
设计或叙述解决此问题的算法。
给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出
来。
如果程序不能正常运行，写出实现此算法中遇到的问题和改进方法；
2．对题目要有相应的源程序
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加
上清晰的程序注释。(注释量占总代码的四分之一)
程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；
3．最后提供的主程序可以象一个应用系统一样有主窗口，通过主菜单和分级菜单调用课程
设计中要求完成的各个功能模块，调用后可以返回到主菜单，继续选择其他功能进行其他功
能的选择。
二叉树的建立与遍历
[问题描述]
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
[基本要求]
从键盘接受输入，以二叉链表作为存储结构，建立二叉树，并对其进行遍历（先序、中
序、后序），将遍历结果打印输出。
以下是我的数据结构实验的作业：肯定好用，里面还包括了统计树的深度和叶子数！记住每
次做完一个遍历还要重新输入你的树哦！
#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T){
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
}
return T;
}
void Preorder(BiTree T){
if(T){
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int Sumleaf(BiTree T){
int sum=0,m,n;
if(T){
if((!T->lchild)&&(!T->rchild))
sum++;
m=Sumleaf(T->lchild);
sum+=m;
n=Sumleaf(T->rchild);
sum+=n;
}
return sum;
}
void zhongxu(BiTree T){
if(T){
zhongxu(T->lchild);
printf("%c",T->data);
zhongxu(T->rchild);
}
}
void houxu(BiTree T){
if(T){
houxu(T->lchild);
houxu(T->rchild);
printf("%c",T->data);
}
}
int Depth(BiTree T){
int dep=0,depl,depr;
if(!T) dep=0;
else{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
main(){
BiTree T;
int sum,dep;
T=Create(T);
Preorder(T);
printf("\n");
zhongxu(T);
printf("\n");
houxu(T);
printf("\n");
sum=Sumleaf(T);
printf("%d",sum);
dep=Depth(T);
printf("\n%d",dep);
}
在Turbo C的环境下，先按Ctrl+F9运行程序，此时就是建立二叉树的过程，例如输入序列
ABC##DE#G##F###（其中的“#”表示空，并且输入过程中不要加回车，因为回车也有对应的
ASCII码，是要算字符的，但是输入完之后可以按回车退出），然后再按ALT+F5显示用户
界面，这时候就能够看到结果了。
另外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否则你怎么输入，
按最后按多少回车程序也不会结束！
