#include <stdio.h>
#include <stdlib.h>>
const int MAX=20;
typedef struct Node
{
char data;
struct Node*lchild;
struct Node*rchild;
}BiTreeNode;
//构造二叉树
//1.按照先序遍历，利用递归构造
//ABD#G##EH##I##CF#J###
void CreateBiTree_PreOrder(BiTreeNode **T) //注意传的是指针的指针
{
char ch;
scanf("%c",&ch);
if('#'==ch)
*T=NULL;
else
{
*T=(BiTreeNode*)malloc(sizeof(BiTreeNode));
if(NULL==*T)
exit(-1);
(*T)->data=ch;
CreateBiTree_PreOrder(&(*T)->lchild);
CreateBiTree_PreOrder(&(*T)->rchild);
}
}
//BiTreeNode* CreateBiTree_PreOrder(BiTreeNode *T) //传的指针
//{
// char ch;
// scanf("%c",&ch);
// if('#'==ch)
// T=NULL;
// else
// {
// T=(BiTreeNode*)malloc(sizeof(BiTreeNode));
// if(NULL==T)
// exit(-1);
// T->data=ch;
// T->lchild=T->rchild=NULL;
// T->lchild=CreateBiTree_PreOrder(T->lchild);
// T->rchild=CreateBiTree_PreOrder(T->rchild);
// }
// return T;
//}
//2.按照带括号的字符串构造二叉树
/*
思路：a(b(c,d),e(f(,g),h(i)))
'(':表明已创建的节点为双亲节点,入栈。将要创建左孩子节点,用flag=1标记
',' :表明将要创建的节点为右孩子节点。用flag=2标记。
')' :表明左右孩子节点创建和链接完毕，父节点出栈
default:创建节点，并且赋值，判断链接情况
*/
void CreateBiTree_ByString(BiTreeNode**T,char str[])
{
BiTreeNode* Stack[MAX]; //栈用于存储父节点
int top=0,flag=0;
BiTreeNode *p=NULL;
while(*str)
{
switch(*str)
{
case '(':
Stack[top++]=p;
flag=1; //即将创建左节点
break;
case ',': flag=2; //即将创建右节点
break;
case ')': --top; //父节点出栈
break;
default:
{
p=(BiTreeNode*)malloc(sizeof(BiTreeNode));
if(NULL==p)
return;
if(*T==NULL)
*T=p;
p->data=*str;
p->lchild=p->rchild=NULL;
switch(flag)
{
case 1:
Stack[top-1]->lchild=p;
break;
case 2:
Stack[top-1]->rchild=p;
break;
}
break;
}
} //switch(*str) end
++str;
}
}
//递归先序遍历
PreOrderTraverse_Recur(BiTreeNode *T)
{
if(T)
{
printf("%2c",T->data);
PreOrderTraverse_Recur(T->lchild);
PreOrderTraverse_Recur(T->rchild);
}
}
//非递归先序遍历
/*
思路:先访问父节点，打印。压栈，访问左孩子节点，压栈，直到左孩子为空
然后在访问右孩子节点
*/
void PreOrderTraverse_NoRecur(BiTreeNode*T)
{
BiTreeNode*Stack[MAX];
int top=0;
BiTreeNode *p=T;
while(p||top>0)
{
while(p)
{
printf("%2c",p->data);
Stack[++top]=p; //父节点压栈
p=p->lchild;
}
if(top>0)
{
p=Stack[top--];
p=p->rchild;
}
}
}
//递归中序遍历
void InOrderTraverse_Recur(BiTreeNode*T)
{
if(T)
{
InOrderTraverse_Recur(T->lchild);
printf("%2c",T->data);
InOrderTraverse_Recur(T->rchild);
}
}
//非递归中序遍历
/*
思路:一直压入左孩子,出栈打印节点，压入右孩子
*/
void InOrderTraverse_NoRecur(BiTreeNode*T)
{
BiTreeNode* Stack[MAX];
int top=0;
BiTreeNode*p=T;
while(p||top>0)
{
while(p)
{
Stack[++top]=p;
p=p->lchild;
}
if(top>0)
{
p=Stack[top--];
printf("%2c",p->data);
p=p->rchild;
}
}
}
//递归后序遍历
void AfterOrderTraverse_Recur(BiTreeNode*T)
{
if(T)
{
AfterOrderTraverse_Recur(T->lchild);
AfterOrderTraverse_Recur(T->rchild);
printf("%2c",T->data);
}
}
//非递归后序遍历
/*
1.思路:父节点压栈，直到左节点为NULL，此时不出栈父节点，直接访问右孩子，同时
设定q用于检测是否已经访问过右孩子
*/
void AfterOrderTraverse_NoRecur(BiTreeNode*T)
{
BiTreeNode*Stack[MAX];
int top=0;
BiTreeNode *p=T,*q=NULL; //q用于判断是否访问过
while(p||top>0)
{
while(p) //直到没有左孩子节点
{
Stack[++top]=p;
p=p->lchild;
}
if(top>0)
{
p=Stack[top]; //不出栈直接访问右子树
if(p->rchild==NULL || p->rchild==q) //没有右子树或者右节点已经访问过
{
printf("%2c",p->data);
q=p;
p=NULL; //p置为空，防止再次入栈
top--;
}
else //有右节点，且没被访问过
p=p->rchild;
}
}
}
//非递归后序遍历
/*
2.思路:利用栈先入后出的特点，依次将父节点，右孩子，左孩子压栈
*/
void AfterOrderTraverse_NoRecur_2(BiTreeNode*T)
{
BiTreeNode*Stack[MAX];
int top=0;
BiTreeNode *pre,*cur; //cur为当前节点, pre为前节点
pre=NULL;
Stack[++top]=T; //根节点入栈
while(top>0)
{
cur=Stack[top];
//当前节点为叶子结点或者其孩子已经访问，输出
if((cur->rchild==NULL&&cur->lchild==NULL)||(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
printf("%2c",cur->data);
pre=cur;
top--;
}
else
{
if(cur->rchild)
Stack[++top]=cur->rchild;
if(cur->lchild)
Stack[++top]=cur->lchild;
}
}
}
//销毁二叉树
void DestoryBiTree(BiTreeNode*T)
{
if(T)
{
if(T->lchild)
DestoryBiTree(T->lchild);
if(T->rchild)
DestoryBiTree(T->rchild);
free(T);
}
}
//根据中序和后序遍历创建二叉树 inOreder[]存储中序遍历,afterOrder[]存储后序遍历
BiTreeNode* setBiTree(char inOreder[],char afterOrder[],int m,int n)
{
if(m>n)
return NULL;
BiTreeNode *p=(BiTreeNode*)malloc(sizeof(BiTreeNode));
p->data=afterOrder[n]; //后序遍历最后节点为父节点
p->lchild=p->rchild=NULL;
int i,j;
for(i=m;inOreder[i]!=afterOrder[n];i++)
; //找到父节点在中序遍历中的位置
for(j=n-1;j>=i;j--) //使中序数组和后序数组相对应
afterOrder[j+1]=afterOrder[j];
p->lchild=setBiTree(inOreder,afterOrder,m,i-1);
p->rchild=setBiTree(inOreder,afterOrder,i+1,n);
return p;
}
//中序+先序创建
BiTreeNode* midpreCreate(char mid[],char pre[],int lm,int rm,int lp,int rp)
{
BiTreeNode *p=(BiTreeNode*)malloc(sizeof(BiTreeNode));
p->data=pre[lp];
p->lchild=p->rchild=NULL;
int pos=lm;
while(mid[pos]!=pre[lp])
pos++;
int childlen=pos-lm; //子树在字符串中的范围
if(pos>lm) //创建左子树
p->lchild=midpreCreate(mid,pre,lm,pos-1,lp+1,lp+childlen);
if(pos<rm)
p->rchild=midpreCreate(mid,pre,pos+1,rm,lp+childlen+1,rp);
return p;
}
//中序+后序创建
BiTreeNode* midpostCreate(char mid[],char post[],int lm,int rm,int lp,int rp)
{
BiTreeNode *p=(BiTreeNode*)malloc(sizeof(BiTreeNode));
p->data=post[rp];
p->lchild=p->rchild=NULL;
int pos=lm;
while(mid[pos]!=post[rp])
pos++;
int childlen=pos-lm; //子树在字符串中的范围
if(pos>lm) //创建左子树
p->lchild=midpostCreate(mid,post,lm,pos-1,lp,lp+childlen-1);
if(pos<rm)
p->rchild=midpostCreate(mid,post,pos+1,rm,lp+childlen,rp-1);
return p;
}
int main()
{
//ABD#G##EH##I##CF#J###
// BiTreeNode *T=NULL;
// CreateBiTree_PreOrder(&T);
// puts("递归先序遍历:");
// PreOrderTraverse_Recur(T);
puts("\n--按照带括号的字符串输入------------");
BiTreeNode *T2=NULL;
char str[]="a(b(c,d),e(f(,g),h(i)))";
CreateBiTree_ByString(&T2,str);
puts("递归先序遍历:");
PreOrderTraverse_Recur(T2);
puts("");
// puts("非递归先序遍历:");
// PreOrderTraverse_NoRecur(T2);
// puts("");
// puts("递归中序遍历:");
// InOrderTraverse_Recur(T2);
// puts("");
// puts("非递归中序遍历:");
// InOrderTraverse_NoRecur(T2);
// puts("");
//
// puts("递归后序遍历:");
// AfterOrderTraverse_Recur(T2);
// puts("");
// puts("非递归后序遍历1:");
// AfterOrderTraverse_NoRecur(T2);
// puts("");
// puts("非递归后序遍历2:");
// AfterOrderTraverse_NoRecur_2(T2);
//
// DestoryBiTree(T2); //销毁二叉树
char inOrder[]={'c','b','d','a','f','g','e','i','h'};
char afterOrder[]={'c','d','b','g','f','i','h','e','a'};
char pre[]={'a','b','c','d','e','f','g','h','i'};
// BiTreeNode *T3=setBiTree(inOrder,afterOrder,0,sizeof(inOrder)-1); //调用后改变后序数组
// PreOrderTraverse_Recur(T3);
BiTreeNode *T4=midpostCreate(inOrder,afterOrder,0,sizeof(inOrder)-1,0,sizeof(inOrder)-1);
puts("\n中+后:");
PreOrderTraverse_Recur(T4);
BiTreeNode *T5=midpreCreate(inOrder,pre,0,sizeof(inOrder)-1,0,sizeof(inOrder)-1);
puts("\n中+先:");
PreOrderTraverse_Recur(T5);
}
