加文

在这个世界上取得成就的人,都努力去寻找他们想要的机会,如果找不到机会,他们便自己创造机会。 -- 萧伯纳
随笔 - 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 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 阅读(428) 评论(0)  编辑 收藏 引用 所属分类: 常用算法


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