poj2418二叉查找树
2012-08-01 09:45:46      个评论

就一个标准查找，我简单用了二叉查找树
[cpp]
#include <iostream>
#include <string>
using namespace std;

class TreeNode

public:
TreeNode();
TreeNode(char str[]);
char name[40];
int number;
TreeNode *leftChild;
TreeNode *rightChild;
};

TreeNode::TreeNode()

number=0;
leftChild=NULL;
rightChild=NULL;

TreeNode::TreeNode(char str[])

strcpy(name,str);
number=1;
leftChild=NULL;
rightChild=NULL;

void InsertTreeNode(TreeNode **treeRoot,char tname[40])

if(*treeRoot==NULL)
{
*treeRoot=new TreeNode(tname);
return;
}

TreeNode *curNode=*treeRoot;
TreeNode *lastNode=NULL;
while(curNode!=NULL)
{
lastNode=curNode;
if(strcmp(curNode->name,tname)==0)
{
curNode->number++;
break;
}
if(strcmp(curNode->name,tname)<0)
{
curNode=curNode->rightChild;
}
else
{
curNode=curNode->leftChild;
}
}

if(curNode==NULL)
{
TreeNode *newNode=new TreeNode(tname);
if(strcmp(lastNode->name,newNode->name)>0 )
{
lastNode->leftChild=newNode;
}
else
{
lastNode->rightChild=newNode;
}
}
return ;

void PreOrder(TreeNode *treeNode,double sum)

if(treeNode==NULL)
return;
PreOrder(treeNode->leftChild,sum);
printf("%s %.4f\n",treeNode->name,treeNode->number/sum*100);
//cout<<treeNode->name<<" "<<treeNode->number<<endl;
PreOrder(treeNode->rightChild,sum);
return;

int main()

TreeNode *treeRoot=NULL;
char charName[40];
double totalNumber=0;
while(gets(charName)!=NULL)
{
if(charName[0]=='\0')break;
totalNumber+=1;
InsertTreeNode(&treeRoot,charName);
}
PreOrder(treeRoot,totalNumber);
return 0;