 |
| 文件: | bintree.rar |
| 大小: | 7KB |
| 下载: | 下载 |
|
不知道什么原因，又看到了数据结构的二叉搜索树，突然有个想法用C++模板和仿函数去实现，这样既可以锻炼下C++模板功力，又可以看看仿函数真实内幕，何乐而不为！
既然要写就要写的清楚明白，把自己所想、所学写出(尽管自己是程序新手)，让浏览或参考的人看的请明了，或指出瑕疵，或有所心得！
1、C++模板类声明跟实现都放在头文件，故此命名为binSearchTree.h的头文件，该文件包含一个二叉搜索树节点类，一个二叉搜索树类；
2、仿函数类放在文件cmpFunc.h中，包括string类型和内置内型的比较实现
3、测试数据来源，每个写的数据结构都要去测试，那必须有随机数生成接口，我把声明定义于random.h中，实现random.cpp中；其中有随机数生成的测试用例test_random.cpp
4、、测试用例，test_tree.cpp中，最后是makefile的书写；
代码如下(附件包括所有文件可以下载)：
1、仿函数类
说明：对string类型和内置类型分别实现了相应的比较函数，放在名字空间bill
/*
* cmpFunc.h
*
* Created on: 2010-12-25
* Author: Administrator
*/
#ifndef CMPFUNC_H_
#define CMPFUNC_H_
#include <cstring>
namespace bill
{
//仿函数针对string
class CmpStr{
public:
int operator()(const std::string& str1,const std::string& str2)
{
return operator ()(str1.c_str(),str2.c_str());
}
int operator()(const char* str1,const char* str2)
{
return strcmp(str1,str2);
}
};
/*仿函数模板类针对int float double*/
template<typename Class>
class Cmp{
public:
int operator()(const Class& first,const Class& second){
return (first - second);
}
};
}
#endif /* CMPFUNC_H_ */
|
2、二叉搜索树模板类
说明：实现大部分功能插入、删除、检索，其他扩展功能请大家自行添加！
/*
* binSearchTree.h
*
* Created on: 2010-12-23
* Author: Administrator
* 模板书写二叉搜索树
*/
#ifndef BINSEARCHTREE_H_
#define BINSEARCHTREE_H_
#include <iostream>
namespace bill {
/*二叉树节点模板类*/
template<typename Class>
class BinNode {
public:
BinNode(const Class& _data,BinNode<Class> *lt = NULL,BinNode<Class> *rt = NULL,BinNode<Class> *_parent = NULL)
:data(_data),left(lt),right(rt),parent(_parent){
count = 1;
}
~BinNode(){ left = right = parent = NULL; count = 0; }
public:
Class data; //节点数据
BinNode<Class> *left; //节点左孩子
BinNode<Class> *right; //节点右孩子
BinNode<Class> *parent; //节点父节点
unsigned int count; //该数据的个数
};
/*二叉搜索树模板类*/
template<typename Class, typename Compare>
class BinSearchTree {
public:
BinSearchTree() { cmp = new Compare(); root = NULL; uNodeCount = 0; }
~BinSearchTree(){ destroyBinTree(); }
int insert(const Class& data);
int remove(const Class& data);
bool search(const Class& data);
const Class& findMax() const; //未实现
const Class& findMin() const; //未实现
const Class& getRootData() const { return root->data; }
int getNodeCount() const { return uNodeCount; }
void Inorder() const { visitInorder(root); }//递归实现
void visitPrevorder() const;//未实现
void visitPostorder() const;//未实现
void destroyBinTree() //消毁二叉搜索树
{
if(root != NULL)
{
destroyBinNode(root);
}
delete cmp;
}
BinNode<Class>* searchNodeAndParent(const Class& data,BinNode<Class>*& parent = NULL)
{
BinNode<Class>* pNode = root;
while(pNode != NULL)
{
parent = pNode->parent;
int nRet = (*cmp)(pNode->data,data);
if(nRet != 0)
{
parent = pNode;
if(nRet < 0)
{
pNode = pNode->right;
}
else
{
pNode = pNode->left;
}
}else{
return pNode;
}
}
return NULL;
}
private:
BinNode<Class> *root; //根节点
unsigned int uNodeCount; //节点数目
Compare *cmp; //比较函数
void visitInorder(BinNode<Class> *node = NULL) const;
BinNode<Class>* searchNode(const Class& data)//搜索数据为data的节点
{
BinNode<Class>* pNode;
pNode = root;
while(pNode != NULL)
{
int nRet = (*cmp)(pNode->data,data);
if(nRet < 0)
{
pNode = pNode->right;
}else if(nRet > 0)
{
pNode = pNode->left;
}
else
{
return pNode;
}
}
return NULL;
}
//private functions
void destroyBinNode(BinNode<Class> *node) //递归销毁节点
{
if(node->left != NULL)
{
destroyBinNode(node->left);
}
if(node->right != NULL)
{
destroyBinNode(node->right);
}
delete node;
}
};
template<typename Class, typename Compare>
bool BinSearchTree<Class,Compare>::search(const Class& data)
{
BinNode<Class> *pNode = searchNode(data);
if(pNode != NULL)
{
return true;
}
else
{
return false;
}
}
template<typename Class, typename Compare>
int BinSearchTree<Class,Compare>::insert(const Class& data)
{
BinNode<Class> *pNode;
BinNode<Class> *pParent = NULL;
BinNode<Class> *pNewNode;
pNode = searchNodeAndParent(data,pParent);//搜索不成功时,可能根为NULL
pNewNode = new BinNode<Class>(data);
if(pNewNode == NULL)
{
return -1; //失败
}
if(pNode != NULL) //已经有该数据
{
pNode->count++; //递增它的个数
}
else
{
if(root == NULL)
{
root = pNewNode;
uNodeCount++;
}
else
{
if(pParent == NULL)
pParent = root;
int nRet = (*cmp)(pParent->data,data);
if(nRet < 0)
{
pParent->right = pNewNode;
}
else
{
pParent->left = pNewNode;
}
pNewNode->parent = pParent;
uNodeCount++;
}
}
return 1;
}
template<typename Class, typename Compare>
int BinSearchTree<Class,Compare>::remove(const Class& data)
{
BinNode<Class> *pNode;
BinNode<Class> *pParentNode;
BinNode<Class> *pMaxNode;
BinNode<Class> *pParentMaxNode;
int nRet = 0;
if(root == NULL)
{
return -1;
}
pParentNode = NULL;
pNode = searchNodeAndParent(data,pParentNode);
if(pNode == NULL)
{
return -1; //搜索失败
}
/*第一种情况,pNode两字节点都不为空时*/
if(pNode->left != NULL && pNode->right != NULL)
{
pMaxNode = pNode->left;
pParentMaxNode = pNode;
while(pMaxNode->right != NULL)
{
pParentMaxNode = pMaxNode;
pMaxNode = pMaxNode->right;
}
pNode->data = pMaxNode->data;
if(pMaxNode == pNode->left)
{
pNode->left = pMaxNode->left;
}
else
{
pParentMaxNode->right = pNode->left;
}
delete pMaxNode;
return 1;
}
if(pNode->left != NULL)
{
pMaxNode = pNode->left;
}else if(pNode->right != NULL)
{
pMaxNode = pNode->right;
}
if(pNode == root)
{
root = pMaxNode;
}else{
if(pParentNode->left == pNode)
{
pParentNode->left = pMaxNode;
}
else
{
pParentNode->right = pMaxNode;
}
}
delete pNode;
return 1;
}
template<typename Class, typename Compare>
void BinSearchTree<Class,Compare>::visitInorder(BinNode<Class>* node) const
{
if(node != NULL)
{
visitInorder(node->left);
std::cout<<node->data<<"["<<node->count<<"] ";
visitInorder(node->right);
}
}
} // namespace bill
#endif /* BINSEARCHTREE_H_ */
|
3、随机数生产类
一个简单测随机数生成类，见附件代码
4、测试用例与Makefile
说明：简单的测试用例以及Makefile文件编写(g++)
/*
* tree.cpp
*
* Created on: 2010-12-24
* Author: Administrator
*/
#include "binSearchTree.h"
#include <iostream>
#include "random.h"
#include "cmpFunc.h"
/*测试用例1(内置类型)*/
void TestCaseForInteger()
{
const int size = 10000;
bill::BinSearchTree<int,bill::Cmp<int> > binSearchTree;
bill::Random random;
int rand[size];
int i = 0;
int search_key;
random.seed(2011);
for(i = 0; i < size; ++i)
{
rand[i] = random.random(0,size);
}
for(i = 0; i < size; ++i)
binSearchTree.insert(rand[i]);
binSearchTree.Inorder();
while(std::cin>>search_key)
{
if(binSearchTree.search(search_key))
{
binSearchTree.remove(search_key);
//binSearchTree.Inorder();
std::cout<<"删除成功!"<<std::endl;
}
else{
std::cout<<"没有该数据，删除失败!"<<std::endl;
}
}
}
void TestCaseForStr()
{
bill::BinSearchTree<std::string,bill::CmpStr> binSearchTree;
std::string strs[] = {"libin","hello","world","liying","china","American","Japness"};
for(int i = 0; i < 7; ++i)
binSearchTree.insert(strs[i]);
binSearchTree.Inorder();
}
int main(int argc, char**argv) {
TestCaseForInteger();
TestCaseForStr();
return 0;
}
|
#Makfile
#
# Created on: 2010-12-25
# Author: Administrator
CXX = g++
CFLAGS = -w -O2
TARGET = test_tree.exe
OBJECTS = test_tree.o random.o
all: $(TARGET)
$(TARGET): test_tree.o random.o
$(CXX) $(CFLAGS) -o $@ $^
$(OBJECTS): %.o : %.cpp
$(CXX) $(CFLAGS) -c -o $@ $<
clean:
@rm -rf $(TARGET) *.o
dist:
tar -zcvf bintree.tar.gz ./*
|
5、扩展与源代码下载
如果写出好的分词程序，就可以配合起来实现简单的词典构建，那会更好的去测试它，更所谓英雄需要美女，不错！不过搜索引擎的词典构建常用AVL和红黑树或其他结构哈希AVL或哈希红黑树，那可能要等我有时间才去写了！
 |
| 文件: | bintree.tar.gz |
| 大小: | 3KB |
| 下载: | 下载 |
|
源代码
阅读(1163) | 评论(1) | 转发(0) |
