// 实现二叉树的先序、中序和后序遍历
#define MAX 30 //二叉树中最多结点数
#define NULL 0
#include <stdlib.h>
#include <stdio.h>
typedef struct btnode //二叉树的结点类型
{
char data;
struct btnode *lchild,*rchild;
}bttree;
bttree *cre_tree(char *str,int i,int m) //将字符串中的第i个字符到第个m字符作为数据生成对应的满二叉树
{
bttree *p;
if(i>m) //无效结点
return NULL;
p=(bttree *)malloc(sizeof(bttree)); //生成新结点
p->data=str[i];
p->lchild=cre_tree(str,2*i+1,m); //创建左子树
p->rchild=cre_tree(str,2*i+2,m); //创建右子树
return p;
}
void lev_order(char s[],int n) //层次遍历,即输出字符数组的元素{
int i;
for(i=0;i<n;i++)
{
printf("%c",s[i]);
printf("->");
}
}
void preorder(bttree *t) //先序遍历二叉树
{
if(t!=NULL)
{
printf("%c",t->data);
if(t->lchild)
{
printf("->");
preorder(t->lchild);
}
if(t->rchild)
{
printf("->");
preorder(t->rchild);
}
}
}
void inorder(bttree *t) //中序遍历二叉树{ if(t!=NULL)
{
inorder(t->lchild);
printf("%c",t->data);
printf("->");
inorder(t->rchild);
}
}
void postorder(bttree *t) //后序遍历二叉树{ if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
printf("->");
}
}
main() //主函数
{
int i,n;
char str[MAX];
bttree *root; //指向根结点的指针
printf("please input a bttree node number:\n");
scanf("%d",&n);
getchar(); //输入数字
printf("please input a string which length is %d:",n); for(i=0;i<n;i++)
str[i]=getchar();
printf("\n\n");
root=cre_tree(str,0,n); //生成二叉树
printf("the tree is already created\n");
//printf("lev_order before swapping:");
//lev_order(root,n);
//printf("\n");
printf("lev_order before swapping:");
lev_order(str,n);
printf("\n");
printf("the result after preorder processing:"); //先序遍历结果preorder(root);
printf("\n");
printf("the result after inorder processing:"); //中序遍历结果
inorder(root);
printf("\n");
printf("the result after postorder processing:"); //后序遍历结果postorder(root);
printf("\n\n");
}。