把二叉樹的葉子節點從左到右用鏈表鏈接起來
#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;
}
posted on 2011-12-10 18:16 chxzwj 閱讀(537) 評論(0) 編輯 收藏 引用 所屬分類: 常用算法



