樹
#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;//生成根節(jié)點(diǎn)
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);
}
}
//實(shí)現(xiàn)二叉樹線序，中序及后序
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按先序次序輸入字符序列。#號(hào)表示空指針\n");
CreatBiTree(&T);
printf("\n先序遍歷二叉樹得到的節(jié)點(diǎn)序列為：");
PreOrderTraverse(T);
printf("\n中序遍歷二叉樹得到的節(jié)點(diǎn)序列為：");
InOrderTraverse(T);
printf("\n后序遍歷二叉樹得到的節(jié)點(diǎn)序列為：");
PostOrderTraverse(T);
printf("\n中序遍歷二叉樹(非遞歸)得到的節(jié)點(diǎn)序列為：");
InOrder_Norecuision(T);
printf("\n");
system("pause");
}
