二叉搜索树-》poj 1577

http://poj.org/problem?id=1577

#include<iostream>
#include<cstring>
#include<malloc.h>
using namespace std;
#define N 100+2
char str[N][N];
typedef struct node
{
char data;
struct node *ltree,*rtree;
}binary;
binary *root;
void creattree(binary *tree,char character) //构建二叉搜索树
{
if(!root) //从根节点起,若为空,这直接插入数据
{
root=(binary *)malloc(sizeof(binary));
root->data=character;
root->ltree=NULL; //把左右子树置空
root->rtree=NULL;
}
else
{
if(character<tree->data) //如果数据小于父节点,查找左子树
{
if(!tree->ltree) //左子树为空,插入
{
tree->ltree=(binary *)malloc(sizeof(binary));
tree->ltree->data=character;
tree->ltree->ltree=NULL;
tree->ltree->rtree=NULL;
}
else
{
creattree(tree->ltree,character); //左子树非空,递归查找左子树直至为空
}
}
else
{
if(!tree->rtree) //处理右子树同左子树
{
tree->rtree=(binary *)malloc(sizeof(binary));
tree->rtree->data=character;
tree->rtree->rtree=NULL;
tree->rtree->ltree=NULL;
}
else
{
creattree(tree->rtree,character);
}
}
}
}

void preorder(binary *h) //前序遍历的递归算法
{
if(h)
{
cout<<h->data;
preorder(h->ltree);
preorder(h->rtree);
}
}

int main()
{
int flag=1;
while(flag)
{
int count=0;
while(cin>>str[count])
{
if(str[count][0]=='*')
break;
if(str[count][0]=='$')
{
flag=0;
break;
}
count++;
}
root=NULL;
for(int i=count-1;i>=0;i--) //从后向前,从根节点开始
{
int len=strlen(str[i]);
for(int j=0;j<len;j++)
{
creattree(root,str[i][j]);
}
}
preorder(root);
cout<<endl;
}
return 0;
}



评论

© 现实给了梦想多少时间 | Powered by LOFTER