用C语言建立一棵含有n个结点的二叉树，采用二叉链表存储，然后分别实现前序，中序，后序遍历该二叉树

Question

如题所述

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define max 100

typedef struct node{ //二叉树结构
char data;
struct node *lc,*rc; //左右子树
}bt,*list;
/*
二叉树
A
/ \
B C
/ \ \
D E F
/ / \
K G H

input
ABDK000E00C0FG00H00

ouput
ABDKECFGH
KDBEACGFH
KDEBGHFCA
*/

int creat(list*root){ //创建一棵二叉树，root使用的是二维指针
char n;
scanf(" %c",&n); //注%C前面加空格是为了起间隔作用 scanf不读入空格
if (n=='0') //0为间隔
{
*root=NULL; return 0; //输入结束
}
*root=(list)malloc(sizeof(bt));
if (!*root) return 0;
(*root)->data=n;
creat(&(*root)->lc);
creat(&(*root)->rc);
return 1;
}

int pre(list root){ //先序遍历
if (!root) return 0;
printf("%c",root->data);
pre(root->lc);
pre(root->rc);
return 1;
}
int mid(list root){ //中序遍历
if (!root) return 0;
mid(root->lc);
printf("%c",root->data);
mid(root->rc);
return 1;
}

int bh(list root){ //后序遍历
if (!root) return 0;
bh(root->lc);
bh(root->rc);
printf("%c",root->data);
return 1;
}
int sum(list root,int *cnt){ //求结点的个数sum
if(root){
(*cnt)++;
sum(root->lc,cnt);
sum(root->rc,cnt);
return 1;
}
return 0;
}
int sumleaf(list root,int *cnt){ //求叶子节点的个数
if (root)
{
if ((!root->lc)&&(!root->rc))
{ (*cnt)++; }
sumleaf(root->lc,cnt);
sumleaf(root->rc,cnt);
return 1;
}
return 0;
}
int deep(list root,int *cnt){ //求深度
if (!root)
{
*cnt=0; return 0;
}
int m,n;
n=m=*cnt;
deep(root->lc,&m);
deep(root->rc,&n);
*cnt=m+1;
if(m<n) *cnt=n+1;
return 1;
}
int floor(list root){ //层次遍历
if(root)
{
list s[max]; int front,rear; //用队进行存储
front=-1; rear=0; s[rear]=root; //初始化
while (rear!=front) //当队为空时结束
{
printf("%c",s[++front]->data);
if (s[rear]->lc)
{s[1+rear]=s[rear]->lc; rear++; } //将左子树存入队列中
if (s[rear]->rc)
{s[1+rear]=s[rear]->rc; rear++; } //将右子书存入队列中
}
return 1;
}
return 0;
}
int scop(list *r,list *p){ //树的复制
if(*r){
*p=(list)malloc(sizeof(bt));
if(*p){
(*p)->data=(*r)->data;
scop(&(*r)->lc,&(*p)->lc);
scop(&(*r)->rc,&(*p)->rc);
return 1;
}
}
*p=NULL;
return 0;
}
int sepect(list root,list *p,char e){ //查找节点返回指针*p p为二级指针
if(root){
if (root->data==e)
{ *p=root; return 1;
}
sepect(root->lc,p,e);
sepect(root->rc,p,e);
}
return 0;
}
void main(){
list b,s,m;
int n,t=1;
char ch='\0';
printf("***********Bitree************\n");
while(t){ //循环操作
printf("input a tree(int):\n");
s=m=b=NULL; //二叉树的初始化
creat(&b);
//按三种遍历输出二叉树
printf("\npre "); pre(b);
printf("\nmid "); mid(b);
printf("\nbh "); bh(b); printf("\n");
//求节点数目，叶子节点的个数，深度
n=0; sum(b,&n); printf("sumdata: %d\n",n);
n=0; sumleaf(b,&n); printf("sumleaf: %d\n",n);
n=0; deep(b,&n); printf("deep: %d\n",n);
//二叉树的复制
scop(&b,&s);
printf("\nscopy tree:\npre ");
pre(s); printf("\nmid ");
mid(s); printf("\nbh ");
bh(s); printf("\n");
//查找节点
printf("sepect a data:\n");
scanf(" %c",&ch); //注%C前面加空格是为了起间隔作用 scanf不读入空格
sepect(b,&m,ch);
if(m)
printf("sepect : %c \n",m->data);
else
printf("Error,no this data: %c\n",ch);
//继续则输入 1，退出输入 0
printf("continue input 1,break input 0:\n");
scanf("%d",&t);
}
}