/*1、二叉树的创建和遍历演示
1）从键盘输入二叉树的各结点值，按先序递归方式创建二叉树
2）分别实现先序、中序、后序递归遍历二叉树
3）输出二叉树的按层次遍历序列
4）输出二叉树的中序非递归遍历下的结点访问次序
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode;
//按先序递归遍历创建二叉树
BiTNode *CreateBitree()
{
char ch;
BiTNode *root;
ch=getchar();
if(ch==' ') root=NULL;
else
{
root=(BiTNode *)malloc(sizeof(BiTNode));
root->data =ch;
root->lchild =CreateBitree();
root->rchild =CreateBitree();
}
return root;
}
//先序递归遍历
void PreOrderTraverse(BiTNode *T)
{
if(T!=NULL)
{
printf("%c",T->data );
PreOrderTraverse(T->lchild );
PreOrderTraverse(T->rchild );
}
}
//中序递归遍历
void InOrderTraverse(BiTNode *T)
{
if(T!=NULL)
{
PreOrderTraverse(T->lchild );
printf("%c",T->data );
PreOrderTraverse(T->rchild );
}
}
//后序递归遍历
void PostOrderTraverse(BiTNode *T)
{
if(T!=NULL)
{
PreOrderTraverse(T->lchild );
PreOrderTraverse(T->rchild );
printf("%c",T->data );
}
}
void main()
{
BiTNode *T;
printf("按先序递归遍历创建二叉树:\n");
T=CreateBitree();
printf("\n");
printf("按先序递归遍历二叉树:\n");
PreOrderTraverse(T);
printf("\n");
printf("按中序递归遍历二叉树:\n");
InOrderTraverse(T);
printf("\n");
printf("按后序递归遍历二叉树:\n");
PostOrderTraverse(T);
printf("\n");
}
