二叉树的遍历_二叉树及其遍历
二叉树的遍历由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树及其遍历”。
# include # include typedef int Etype;typedef struct BiTNode /* 树结点结构 */
{ Etype data;
struct BiTNode *lch,*rch;
}BiTNode;/* 函数原形声明 */ BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void numb1(BiTNode *p);void numb2(BiTNode *p);void numb3(BiTNode *p);BiTNode *t;int n,n0,n1,n2;/* 主函数 */ main(){ char ch;int k;
do { printf(“nnn”);
printf(“nn
1.建立二叉树方法1 ”);
printf(“nn
2.建立二叉树方法2”);
printf(“nn
3.前序递归遍历二叉树”);
printf(“nn
4.中序递归遍历二叉树”);
printf(“nn
5.后序递归遍历二叉树”);
printf(“nn
6.前序计算树中结点个数”);
printf(“nn
7.中序计算树中结点个数”);
printf(“nn
8.后序计算树中结点个数”);
printf(“nn
9.结束程序运行”);
printf(“n======================================”);
printf(“n
请输入您的选择(1-9)”);scanf(“%d”,&k);
switch(k)
{ case 1:t=creat_bt1();break;/* 调用性质5建立二叉树算法 */
case 2:t=creat_bt2();break;/* 调用递归建立二叉树算法
*/
case 3: { preorder(t);
/* 调用前序遍历
*/
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 4: { inorder(t);
/* 调用中序遍历
*/
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 5: { postorder(t);
/* 调用后序遍历
*/
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 6:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb1(t);
printf(“n
二叉树结点总数 n=%d”,n);
printf(“n
二叉树叶子结点数 n0=%d”,n0);
printf(“n
度为1的结点数 n1=%d”,n1);
printf(“n
度为2的结点数 n2=%d”,n2);
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 7:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb2(t);
printf(“n
二叉树结点总数 n=%d”,n);
printf(“n
二叉树叶子结点数 n0=%d”,n0);
printf(“n
度为1的结点数 n1=%d”,n1);
printf(“n
度为2的结点数 n2=%d”,n2);
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 8:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */
numb3(t);
printf(“n
二叉树结点总数 n=%d”,n);
printf(“n
二叉树叶子结点数 n0=%d”,n0);
printf(“n
度为1的结点数 n1=%d”,n1);
printf(“n
度为2的结点数 n2=%d”,n2);
printf(“nn
打回车键，继续。”);ch=getch();
} break;
case 9: exit(0);
} /* switch */
printf(“n----------------”);
}while(k>=1 && k
printf(“n
再见！”);
printf(“n
打回车键，返回。”);ch=getch();} /* main */
/* 利用二叉树性质5，借助一维数组V 建立二叉树 */ BiTNode *creat_bt1(){ BiTNode *t,*p,*v[20];int i,j;Etype e;
/* 输入结点的序号i、结点的数据e */
printf(“n 序号i,数据data=?”);scanf(“%d%d”,&i,&e);
while(i!=0 && e!=0)
/* 当 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 i,data=?”);scanf(“%d%d”,&i,&e);
}
return(t);} /* creat_bt1 */ /* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2()
{ BiTNode *t;
int e;
printf(“n data=”);scanf(“%d”,&e);
if(e==0)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 preorder(BiTNode *p){ if(p){
printf(“%3d”,p->data);
preorder(p->lch);
preorder(p->rch);
} } /* preorder */ /* 中序递归遍历二叉树
*/ void inorder(BiTNode *p){ if(p){ inorder(p->lch);
printf(“%3d”,p->data);
inorder(p->rch);
} } /* inorder */ /* 后序递归遍历二叉树
*/ void postorder(BiTNode *p){ if(p){
postorder(p->lch);
postorder(p->rch);
printf(“%3d”,p->data);
} } /* posorder */ /* 利用前序递归遍历二叉树的方法，计算树中结点个数 */ void numb1(BiTNode *p){ if(p){
{ 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++;
}
numb1(p->lch);
numb1(p->rch);
} } /* numb1 */
/* 利用中序递归遍历二叉树的方法，计算树中结点个数 */ void numb2(BiTNode *p){ if(p){ numb2(p->lch);
{ 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++;
}
numb2(p->rch);
} } /* numb2 */
/* 利用后序递归遍历二叉树的方法，计算树中结点个数 */ void numb3(BiTNode *p){ if(p){ numb3(p->lch);
numb3(p->rch);
{ 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++;
}
} } /* numb3 */
