#include <iostream>
using namespace std;
#define STACK_MAX_SIZE 50
typedef struct node
{
char data;
node * lchild;
node * rchild;
}* BTreeNode;
void CreateBTree(BTreeNode &root,char * a)
{
BTreeNode temp;
BTreeNode Stack[STACK_MAX_SIZE];
int top =-1;
int k;
int i=0;
root = NULL;
while(a[i]!='\0')
{
switch(a[i])
{
case '#':
break;
case '(':
if(top == STACK_MAX_SIZE-1)
{
cout<<"栈溢出！程序自动退出！！"<<endl;
exit(1);
}
else
{
top ++;
Stack[top] = temp;
k=1;
break;
}
case ')':
if(top ==-1)
{
exit(1);
} else
{
top--;
break;
}
case ',':
k = 2;
break;
default:
temp = new node();
temp->data = a[i];
temp->lchild = NULL;
temp->rchild = NULL;
if(root == NULL)
{
root = temp;
}
else
{
if(k==1)
Stack[top]->lchild = temp;
else
{
Stack[top]->rchild = temp;
}
}
}
i++;
}
}
void PreSort(BTreeNode root)
{
if(root == NULL)
{
return ;
}
else
{
cout<<root->data<<" ";
PreSort(root->lchild);
PreSort(root->rchild);
}
}
void NRPresort(BTreeNode root)
{
BTreeNode temp = root;
BTreeNode stack[STACK_MAX_SIZE];
int top = -1;
while(!(temp == NULL && top == -1))
{
while(temp!=NULL)
{
cout<<temp->data<<" ";
stack[++top] = temp;
temp = temp->lchild;
}
if(top == -1)
return ;
else
{
temp = stack[top--];
temp = temp->rchild;
}
}
}
void InSort(BTreeNode root)
{
if(root == NULL)
{
return ;
}
else
{
InSort(root->lchild);
cout<<root->data<<" ";
InSort(root->rchild);
}
}
void NRInSort(BTreeNode root)
{
BTreeNode temp = root;
BTreeNode stack[STACK_MAX_SIZE];
int top = -1;
while(!(temp == NULL && top == -1))
{
while(temp!=NULL)
{
stack[++top] = temp;
temp = temp->lchild;
}
if(top == -1)
return ;
else
{
temp = stack[top--];
cout<<temp->data<<" ";
temp = temp->rchild;
}
}
}
void PostSort(BTreeNode root)
{
if(root == NULL)
{
return ;
}
else
{
PostSort(root->lchild);
PostSort(root->rchild);
cout<<root->data<<" ";
}
}
void NRPostSort(BTreeNode root)
{
typedef struct STACK
{
BTreeNode link;
int flag;
}Stack;
Stack stack[STACK_MAX_SIZE];
BTreeNode temp = root;
int top = -1;
int sign;
while(!(temp == NULL && top == -1))
{
if(temp != NULL)
{
stack[++top].link = temp;
stack[top].flag = 1;
temp = temp->lchild;
}
else
{
temp = stack[top].link;
sign = stack[top--].flag;
if(sign != 2)
{
stack[++top].link = temp;
stack[top].flag = 2;
temp = temp->rchild;
}
else
{
cout<<temp->data<<" ";
temp = NULL;
}
}
}
}
void LevelSort(BTreeNode root)
{
BTreeNode queue[ STACK_MAX_SIZE];
BTreeNode temp = root;
int rear = 0;
int front = -1;
queue[rear] = temp;
while(rear != front)
{
cout<<queue[++front]->data<<" ";
if(queue[front]->lchild != NULL)
queue[++rear] = queue[front]->lchild;
if(queue[front]->rchild != NULL)
queue[++rear] = queue[front]->rchild;
}
}
int main()
{
char * a = "E(B(A,D(C,#)),I(G(F,H),J))";
BTreeNode root;
CreateBTree(root,a);
cout<<"先序序列： ";
PreSort(root);
cout<<"\n先序非递归：";
NRPresort(root);
cout<<"\n中序序列： ";
InSort(root);
cout<<"\n中序非递归：";
NRInSort(root);
cout<<"\n后序序列： ";
PostSort(root);
cout<<"\n后序非递归：";
NRPostSort(root);
cout<<"\n层次序列： ";
LevelSort(root);
getchar();
return 0;
}