建立一个二叉树实现二叉树的先序中序后序和遍历。

Question

编写一个程序实现二叉树的先序中序后序和遍历

Answer 1

#include <stdio.h>
#define N 100
typedef struct node
{ char data;
struct node *lchild,*rchild;
}BTNode;

/*---二叉树的建立---*/
BTNode *createbintree()
{
BTNode *t;
char x;
scanf("%c",&x);
if (x=='#') t=NULL;
else
{
t=(BTNode *)malloc(sizeof(BTNode));
t->data=x;
t->lchild=createbintree();
t->rchild=createbintree();
}
return(t);
}

/*---先序遍历算法---*/
void preorder(BTNode *t)
{
if(t!=NULL)
{
printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}

/*---中序遍历算法(递归算法)---*/
void inorder(BTNode *t)
{
if(t!=NULL)
{
inorder(t->lchild);
printf("%c ",t->data);
inorder(t->rchild);
}
}

/*---后序遍历算法---*/
void postorder(BTNode *t)
{
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c ",t->data);
}
}

/*---中序遍历算法(非递归算法)---*/
void inorder1(BTNode *t)
{
int i=0;
BTNode *a[N],*p;
if(t==NULL) return;
p=t;
do
{
while(p)
{
a[i++]=p;
p=p->lchild;
}
if(i!=0)
{
p=a[--i];
printf("%c ",p->data);
p=p->rchild;
}
}while(i!=0 || p);
}

/*---互换左右孩子算法---*/
void swap(BTNode *t)
{
BTNode *p;
if(t!=NULL || (t->lchild==NULL && t->rchild==NULL))
{
p=t->lchild;
t->lchild=t->rchild;
t->rchild=p;
swap(t->lchild);
swap(t->rchild);
}
}

/*---选择函数---*/
void select(BTNode *t)
{
int m,n;
printf("\nselect the algorithm\n1. Preorder\n2. Inorder(Recursive)\n3. Inorder(Non-recursive)\n4. Postorder\n5. Swap lchild and rchild\n");
scanf("%d",&m);
switch(m)
{
case 1:preorder(t);break;
case 2:inorder(t);break;
case 3:inorder1(t);break;
case 4:postorder(t);break;
case 5:swap(t);preorder(t);break;
default:printf("ERROR!! Please select again...\n");select(t);
}
printf("\n\n1. Continue\n2. Exit\n");
scanf("%d",&n);
switch(n)
{
case 2:break;
case 1:
default:select(t);
}
}

void main()
{
BTNode *t;
printf("Please input the sequence of the bintree..\nPS:a '#' for NULL\nExample:'AB#C#D##EF##G##'!\n");
printf("\nbintree:");
t=createbintree();
select(t);
}

Answer 2

#include<stdio.h>
#include<stdlib.h>
typedef struct BiT{
char data;
struct BiT *lchild;
struct BiT *rchild;
}BiT;
BiT* CreateBiTree(BiT *T) {
//构造二叉链表表示的二叉树T
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
T = (BiT *)malloc(sizeof(BiT));
T->data = ch;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return T;
}
void PreOrderTraverse(BiT *T) {
// 先序遍历二叉树T
if (T) {
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiT *T) {
// 中序遍历二叉树T
if (T) {
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiT *T) {
// 后序遍历二叉树T
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main() {
printf("先序建树:");
BiT *T=CreateBiTree(T);
printf("\n先序遍历:");
PreOrderTraverse(T);
printf("\n中序遍历:");
InOrderTraverse(T);
printf("\n后序遍历:");
PostOrderTraverse(T);
getchar();getchar();
}