数据结构·二叉树问题·

//头文件
#include
#include
#include//函数结果状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
// typedef 类型定义 Status 函数的类型
typedef int Status ;
typedef char TElemType;typedef struct BitNode //二叉树的链表存储表示
{
TElemType data;
struct BitNode *lchild, *rchild; //左右孩子指针
} BitNode, *BiTree;Status InitBitree(BiTree &T);//初始化一棵二叉树
Status CreateBiTree(BiTree &T);//二叉树的创建（二叉链表）
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)) ;//先序遍历
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)); //中序遍历
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)); //后序遍历Status InitBitree(BiTree &T)//初始化一棵二叉树
{
T=(BiTree)malloc(sizeof(BitNode));
if(!T) exit(OVERFLOW);
T->data=0;
T->lchild=NULL;
T->rchild=NULL;
return OK;
}
Status CreateBiTree(BiTree &T)//二叉树的创建（二叉链表）
{
TElemType e;
scanf("%c",&e);
if(e=='.')T=NULL;
else{
T=(BiTree)malloc(sizeof(BitNode));
if(!T)exit(OVERFLOW);
T->data=e;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}//若元素为字符型则输入时不可随意加空格Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)) //先序遍历
{
if(T){
if( (*visit)(T->data) ) //s1
if( PreOrderTraverse(T->lchild,(*visit))) //s2
if( PreOrderTraverse(T->rchild,(*visit))) //s3
return OK;
return ERROR; //只要有一次访问失败则必执行此语句
}
return OK; //树空时返回OK
}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)) //中序遍历
{
if(T)
{
if( PreOrderTraverse(T->lchild,(*visit))) //s2
if( (*visit)(T->data) ) //s1
if( PreOrderTraverse(T->rchild,(*visit))) //s3
return OK;
return ERROR; //只要有一次访问失败则必执行此语句
}
return OK; //树空时返回OK
}
Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)) //后序遍历
{
if(T)
{
if( PreOrderTraverse(T->lchild,(*visit))) //s2
if( PreOrderTraverse(T->rchild,(*visit))) //s3
if( (*visit)(T->data) ) //s1
return OK;
return ERROR; //只要有一次访问失败则必执行此语句
}
return OK; //树空时返回OK
}
Status PrintElemt (TElemType e) //二叉树的输出
{
printf("%c ",e);
return OK;
}void main ()
{
BiTree T;
InitBitree(T);
printf("请创建一个二叉树:");
CreateBiTree(T);
printf("先序遍历："); PreOrderTraverse(T,PrintElemt); printf("\n");
printf("中序遍历："); InOrderTraverse(T,PrintElemt); printf("\n");
printf("后序遍历："); PostOrderTraverse(T,PrintElemt); printf("\n");
} 经过调试 正确

#include
#include
#include
typedef struct Node
{
char data;
Node *Lchild,*Rchild;
}*BitTree,BitNode;void creat_tree(BitTree *p)
{
char c;
c=getchar();
if(c=='.') *p=NULL;
else
{
(*p)=(BitTree)malloc(sizeof(BitNode));
(*p)->data=c;
creat_tree(&(*p)->Lchild);
creat_tree(&(*p)->Rchild);
}
}
void visit(char c)
{
printf("%c ",c);
}
void Preorder(BitTree p)
{
BitTree s[100];
int top=0;
while (p!=NULL|| top!=0)
{
while (p!=NULL)
{
visit(p->data);
top++;
s[top]=p;
p=p->Lchild;
}
if (top!=0)
{
p=s[top];
top--;
p=p->Rchild;
}

}
}void Postorder(BitTree root)
{
BitNode *p,*q;
BitTree s[100];
int top=0;
q=NULL;
p=root;
while(p||top)
{
while(p)
{
top++;
s[top]=p;
p=p->Lchild;
}
if(top>0)
{
p=s[top];
if((p->Rchild==NULL)||(p->Rchild==q))
{
visit(p->data);
q=p;
top--;
p=NULL;
}
else
p=p->Rchild;
}
}
free(s);
}
int main()
{
BitTree root;
printf("建立二叉树，输入扩展先序遍历序列\n");
creat_tree(&root);
printf("先序序列为：");
Preorder(root);
printf("\n后序序列为：");
Postorder(root);
system("pause");
}