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

Question

如题所述

Answer 1

其实这个程序很简单的。 代码如下：

#include<stdio.h>
#include<malloc.h>
#define MAX_TREE_SIZE  100
typedef struct {
int i;
}TElemType;
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
getchar();
if(ch==' '||ch=='\n')
{
 T=NULL;
}
else{
 T=(BiTNode *)malloc(sizeof(BiTNode));
 T->data=ch;
 CreateBiTree(T->lchild);
 CreateBiTree(T->rchild);
}
return 1;
}//CreateBiTree()
int Visit(char ch)
{
printf("%c",ch);
return 1;
}
int PreOrderTraverse(BiTree T,int (* Visit)(char ch))
{
if(T)
{
 if(Visit(T->data))
  if(PreOrderTraverse(T->lchild,Visit))
   if(PreOrderTraverse(T->rchild,Visit)) return 1;
}else return 1;
}
int InOrderTraverse(BiTree T,int (* Visit)(char ch))
{
if(T)
{
  if(InOrderTraverse(T->lchild,Visit))
   if(Visit(T->data))
    if(InOrderTraverse(T->rchild,Visit)) return 1;
}else return 1;
}
int PostOrderTraverse(BiTree T,int(* Visit)(char ch))
{
if(T)
{
 if(PostOrderTraverse(T->lchild,Visit))
  if(PostOrderTraverse(T->rchild,Visit))
   if(Visit(T->data))  return 1;
}else return 1;
}
void  main()
{
BiTree  T;
printf("从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：\n");
CreateBiTree(T);
printf("先序遍历为：");
PreOrderTraverse(T,Visit);
printf("\n");
printf("中序遍历为：");
InOrderTraverse(T,Visit);
printf("\n");
printf("后序遍历为：");
PostOrderTraverse(T,Visit);
}

Answer 2

#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);
}