Binary Tree is widely employed in many cases as a very important data structrue.
I will take a simple example to introduce it.
Suppose we want to handle the more general problem of counting the occurrences of all the
words in some input.Since the list of words isn't known in advance,we can't conveniently sort it and use a binary search.Yet we can't do a linear search for each word as it arrives,to see if it's already been seen;the program would take a long time.
a binary tree will help us to solve the problem.
terminal:
First we define the node structure,which is used to store the infomation of each word.
it consists of word name,count,two pointer,which point to left subtree and right substree.
secondly,tree structure is a binary sorted tree.
each word has a unique node in the tree.
the detailed code implemention below:
// wordTree.h: interface for the wordTree class.
//
//////////////////////////////////////////////////////////////////////
#ifndef __WORDTREE_
#define __WORDTREE_
class wordTree;
class wordNode
{
friend class wordTree;
private:
char *word;
int count;
wordNode *left,*right;
private:
wordNode(const char* w,wordNode *left=0,wordNode *right=0,int count=1);
~wordNode();
inline void incrcount(){
count++;
}
};
class wordTree
{
public:
wordTree():root(0){
}
virtual ~wordTree(){
freetree(root);
}
void addWord(const char *w);
void printTree();
private:
wordNode* addWord(wordNode *p,const char *w);
void printTree(wordNode *p);
void freetree(wordNode *p);
wordNode* root;
};
#endif // end __WORDTREE_
// wordTree.cpp: implementation of the wordTree class.
//
//////////////////////////////////////////////////////////////////////
#include "wordTree.h"
#include <string.h>
#include <iostream>
wordNode::wordNode(const char* w,wordNode *left/**//* =0 */,wordNode *right/**//* =0 */,int count/**//* =0 */)
{
int len=strlen(w);
word=new char[len+1];
strcpy(word,w);
this->left=left;
this->right=right;
this->count=count;
}
wordNode::~wordNode()
{
if(word!=0)
delete [] word;
}
void wordTree::addWord(const char *w){
root=addWord(root,w);
}
wordNode* wordTree::addWord(wordNode *p,const char *w)
{
int cond;
if(p==0)
p=new wordNode(w);
else if((cond=strcmp(w,p->word))==0)
p->incrcount();
else if (cond<0)
p->left=addWord(p->left,w);
else
p->right=addWord(p->right,w);
return p;
}
void wordTree::printTree()
{
printTree(root);
}
void wordTree::printTree(wordNode *p)
{
if (p==0)
return;
printTree(p->left);
std::cout<<p->word<<" count: "<<p->count<<std::endl;
printTree(p->right);
}
void wordTree::freetree(wordNode *p)
{
if(p==0)
return;
freetree(p->left);
freetree(p->right);
delete p;
}
//test.cpp
//test the example
#include "wordTree.h"
#include <iostream>
#include <string>
int main()
{
wordTree wt;
std::string str;
while (std::cin>>str)
{
wt.addWord(str.c_str());
wt.printTree();
}
}