二叉排序树，又称二叉查找树，左子树结点值一律小于父结点，右子树结点值一律大于父结点，查找平均算法复杂度为O(logn)。
还是那道统计单词数目的题目，使用二叉排序树来解决，查找和插入以及统计数目使用一个函数解决，比使用哈希表的优势在于，中序遍历输出结果，单词是有序的。
程序中需要注意的地方，释放树结点的时候，要使用后续遍历，先释放子结点后才释放根结点。
/**//* -------------------------------------------------------------------------
// 文件名 ： binarytree.h
// 创建者 ： dj
// 创建时间 ： 2008-1-1
// 功能描述 ： 二叉排序树
// -----------------------------------------------------------------------*/
#ifndef __BINARYTREE_H__
#define __BINARYTREE_H__
#define SAFE_DELETE(p) {if(p) { delete [] (p); (p) = NULL;}}
struct TreeNode
{
TreeNode(const char* s):
counter(1), left(NULL), right(NULL)
{
name = new char[strlen(s)+1];
strcpy(name, s);
}
~TreeNode()
{
SAFE_DELETE(name);
}
char* name;
int counter;
TreeNode* left;
TreeNode* right;
};
class BinaryTree
{
public:
BinaryTree():m_pRoot(NULL)
{}
~BinaryTree()
{
FreeTree(m_pRoot);
}
void Lookup(const char* sName)
{
TreeNode** p = &m_pRoot;
while(*p)
{
int cmp = strcmp(sName, (*p)->name);
if (cmp<0)
p = &((*p)->left);
else if (cmp>0)
p = &((*p)->right);
else //found the word
{
((*p)->counter)++; //increase the counter
return;
}
}
// not found, then add the word node.
TreeNode* pNode = new TreeNode(sName);
*p = pNode;
}
void Dump(const char* sFile)
{
ofstream f(sFile);
Travel(m_pRoot, f);
f.close();
}
private:
void Travel(TreeNode* pNode, ofstream& f)
{
if (!pNode)
return;
Travel(pNode->left, f);
f<<pNode->name<<" "<<pNode->counter<<endl;
Travel(pNode->right, f);
}
void FreeTree(TreeNode* pNode)
{
if(!pNode)
return;
FreeTree(pNode->left);
FreeTree(pNode->right);
delete pNode;
}
private:
TreeNode* m_pRoot;
};
#endif //__BINARYTREE_H__int main(int argc, char* argv[])
{
BinaryTree tree;
ifstream f("c:\\ip.txt");
string s;
while(f>>s)
{
tree.Lookup(s.c_str());
}
tree.Dump("c:\\stat.txt");
return 0;
}
posted on 2008-01-01 21:49
小四 阅读(393)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构