|
#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 link(BTreeNode root,node * &head,node * &tail)
  {
if(root != NULL)
 {
if(root->lchild == NULL && root->rchild == NULL)
 {
if(head == NULL)
 {
head = root;
tail = head;
}
else
 {
tail->rchild = root;
tail = root;
}
}
if(root->lchild != NULL) link(root->lchild,head,tail);
if(root->rchild != NULL) link(root->rchild,head,tail);
}
}
void PreOrder(BTreeNode root)
  {
if(root != NULL)
 {
cout<<root->data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
int main()
  {
char * a = "E(B(A,D(C,#)),I(G(F,H),J))";
BTreeNode root;
node * head = NULL;
node * tail = NULL;
node * temp = NULL;
CreateBTree(root,a);
link(root,head,tail);
for(temp = head;temp!=NULL;temp = temp->rchild)
cout<<temp->data<<" ";
getchar();
return 0;
}

|