树
#include<stdio.h>
#include<stdlib.h>
#define MAX 50
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef struct BiTNode{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*BiTree;
Status CreatBiTree(BiTree *T)//先序建立二叉树
{
char ch;
scanf("%c",&ch);
if(ch=='#')(*T)=NULL;
else
{
(*T)=(BiTree)malloc(sizeof(BiTNode));
if(!(*T)) exit(OVERFLOW);
(*T)->data = ch;//生成根节点
CreatBiTree(&((*T)->lchild));
CreatBiTree(&((*T)->rchild));
}
return OK;
}
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T)
{
if(T){
printf("%c",T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{
if(T){
printf("%c",T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
//实现二叉树线序，中序及后序
void InOrder_Norecuision(BiTree T)
{
BiTree stack[MAX];
BiTree p;
int top=0;
p=T;
while(p!=NULL||top!=0)
{
while(p!=NULL)
{
p=stack[top];
printf("%c",p->data);
top++;
p=p->lchild ;
}
if(top>0)
{
top--;
p=stack[top];
printf("%c",p->data);
p=p->rchild ;
}
}
}
void main()
{
BiTree T;
printf("\n按先序次序输入字符序列。#号表示空指针\n");
CreatBiTree(&T);
printf("\n先序遍历二叉树得到的节点序列为：");
PreOrderTraverse(T);
printf("\n中序遍历二叉树得到的节点序列为：");
InOrderTraverse(T);
printf("\n后序遍历二叉树得到的节点序列为：");
PostOrderTraverse(T);
printf("\n中序遍历二叉树(非递归)得到的节点序列为：");
InOrder_Norecuision(T);
printf("\n");
system("pause");
}
