加文

在这个世界上取得成就的人,都努力去寻找他们想要的机会,如果找不到机会,他们便自己创造机会。 -- 萧伯纳
随笔 - 14, 文章 - 56, 评论 - 1, 引用 - 0
数据加载中……

输入广义表建立二叉树

#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);
    }
}
int main()
{
    
char * a = "E(B(A,D(C,#)),I(G(F,H),J))";
    BTreeNode root;
    CreateBTree(root,a);
    cout
<<"先序序列:  ";
    PreSort(root);
    getchar();
    
return 0;
}

posted on 2011-10-26 12:48 chxzwj 阅读(967) 评论(0)  编辑 收藏 引用 所属分类: 常用算法


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理