分享小白代码:二叉树的建立~
这代码是老师的实验课件~拿出来分享一下,或者会对小白有点帮助~大神还是打点酱油就算啦
~
程序代码：
//二叉树的创建及其遍历程序：字符型结点数据
/* 二叉树的建立与遍历 */
# include <stdio.h>
# include <stdlib.h>
typedef char Etype;
typedef struct BiTNode{ /* 树结点结构 */
Etype data;
struct BiTNode *lch,*rch;
}BiTNode;
/* 函数原形声明 */
BiTNode *creat_bt1();
BiTNode *creat_bt2();
void DLR(BiTNode *p);
void LDR(BiTNode *p);
void LRD(BiTNode *p);
void numb(BiTNode *p);
BiTNode *t; int n,n0,n1,n2;
void visitC(Etype dataC);
/* 主函数 */
main(){
char ch; int k;
do {
printf("\n\n\n");
printf("\n\n 1. 建立二叉树方法1(性质5) ");
printf("\n\n 2. 建立二叉树方法2(先序递归)");
printf("\n\n 3. 先序DLR递归遍历二叉树");
printf("\n\n 4. 中序LDR递归遍历二叉树");
printf("\n\n 5. 后序LRD递归遍历二叉树");
printf("\n\n 6. 计算树中结点个数");
printf("\n\n 0. 结束程序运行");
printf("\n======================================");
printf("\n 请输入您的选择 (0，1,2,3,4,5,6)"); scanf("%d",&k);
switch(k){
case 1:t=creat_bt1( );break; /* 调用性质5建立二叉树算法 */
case 2:t=creat_bt2( );break; /* 调用递归建立二叉树算法 */
case 3: {
DLR(t); /* 调用中序遍历 */
printf("\n\n 打回车键，继续。"); ch=getchar();
} break;
case 4: {
LDR(t); /* 调用中序遍历 */
printf("\n\n 打回车键，继续。"); ch=getchar();
} break;
case 5: {
LRD(t); /* 调用中序遍历 */
printf("\n\n 打回车键，继续。"); ch=getchar();
} break;
case 6: {
n=0;n0=0 ; n1=0; n2=0; /* 全局变量置0 */
numb(t);
printf("\n 二叉树结点总数 n=%d",n);
printf("\n 二叉树叶子结点数 n0=%d",n0);
printf("\n 度为1的结点数 n1=%d",n1);
printf("\n 度为2的结点数 n2=%d",n2);
printf("\n\n 打回车键，继续。"); ch=getchar();
} break;
case 0: exit(0);
} /* switch */
printf("\n ----------------");
}while(k>=0 && k<=6);
printf("\n 再见！");
printf("\n 打回车键，返回。"); ch=getchar();
} /* main */
/* 利用二叉树性质5 ，借助一维数组V 建立二叉树 */
BiTNode *creat_bt1(){
BiTNode *t,*p,*v[20]; int i,j; Etype e;
/* 输入结点的序号i 、结点的数据e */
printf("\n结点数据（格式0?结束）i,char=?"); scanf("%d%c",&i,&e);
while(i!=0 && e!='?'){ /* 当 i ,e都为0时，结束循环 */
p=(BiTNode *)malloc(sizeof(BiTNode));
p->data=e; p->lch=NULL; p->rch=NULL;
v[i]=p;
if (i==1) t=p; /* 序号为1的结点是根 */
else{
j=i/2;
if(i%2==0) v[j]->lch=p; /* 序号为偶数，做左孩子*/
else v[j]->rch=p; /* 序号为奇数，做右孩子*/
}
printf("\n结点数据（格式0?结束）i,char=?"); scanf("%d%c",&i,&e);
}
return(t);
} /* creat_bt1 */
/* 模仿先序递归遍历方法，建立二叉树 */
BiTNode *creat_bt2(){
BiTNode *t; Etype e;
scanf("%c",&e); //过滤前面菜单选择留下的回车键
printf("\n如连续输入以空格间隔,/结束分支 char="); scanf("%c",&e);
if(e=='/') t=NULL; /* 对于0值，不分配新结点 */
else {
t=(BiTNode *)malloc(sizeof(BiTNode));
t->data=e;
t->lch=creat_bt2(); /* 左孩子获得新指针值 */
t->rch=creat_bt2(); /* 右孩子获得新指针值 */
}
return(t);
} /* creat_bt2 */
/* 先序递归遍历二叉树 */
void DLR(BiTNode *p){
if (p) {
visitC(p->data); //访问根节点
DLR(p->lch); //先序遍历左子树
DLR(p->rch); //先序遍历右子树
}
} /* inorder */
/* 中序递归遍历二叉树 */
void LDR(BiTNode *p){
if (p) {
LDR(p->lch); //中序遍历左子树
visitC(p->data); //访问根节点
LDR(p->rch); //中序遍历右子树
}
} /* inorder */
/* 后序递归遍历二叉树 */
void LRD(BiTNode *p){
if (p) {
LRD(p->lch); //后序遍历左子树
LRD(p->rch); //后序遍历右子树
visitC(p->data); //访问根节点
}
} /* inorder */
/* 利用中序递归遍历二叉树的方法，计算树中结点个数 */
/* 读者可以试着运用先序或后序递归遍历二叉树方法重新编写这一段函数 */
void numb(BiTNode *p){
if (p) {
numb(p->lch);
visitC(p->data);
//printf("%3d",p->data);
n++;
if(p->lch==NULL && p->rch==NULL) n0++;
if((p->lch==NULL && p->rch!=NULL) || (p->lch!=NULL && p->rch==NULL)) n1++;
if(p->lch!=NULL && p->rch!=NULL) n2++;
/* 把访问的功能扩大了 */
numb(p->rch);
}
} /* numb */
void visitC(Etype dataC){
printf("%c ",dataC);
}
小天过过奖了~那个小白代码还有很多地方可以优化的~只是作为一个参考而已~真的要弄这个需要很大优化
