二叉查找树的模板类实现（一）

现在的位置: 首页 > 综合 > 正文

二叉查找树的模板类实现（一）

2013年01月07日 ⁄ 综合 ⁄ 共 975字 ⁄ 字号小中大 ⁄ 评论关闭

对于模板类一般的编译链接会出错，这是因为模板类并不是一个具体的数据类型，只有将模板类的模板数据类型给定了，模板类才实例化为一个具体的类，然后在定义类对象。
解决办法：
一、将所有的成员函数实现部分放到头文件下面
缺点：这样做的话会使头文件太大，编译链接很慢
二、建立一个新的文件，在新的文件里面实例化这个模板
举例：
现有一个模板类

template<class key, class value>
class BSTree
{
...
};

定义在文件BSTree.h中，实现部分在BSTree.cpp中
在main.cpp中想按照BSTree<int,string>的方式调用这个模板类,则首先建立一个新文件
templateInstanceBSTree.cpp

#include 'BSTree.cpp'
#include <string>
using namespace std;
template class BSTree<int,string>;

然后编译链接的时候使用templateInstanceBSTree.cpp而不是BSTree.cpp
即：
g++ -g -o main templateInstanceBSTree.cpp main.cpp
即可

再议查找树：

二叉查找树是一棵每个节点都含有两个子节点的二叉树
并且父节点的关键字值大于左子树所有节点的关键字值，而小于右子树所有节点关键字值
二叉查找树的主要操作是

get(key) //查找-------------------------------O(n)
insert()//插入--------------------------------O(n)
remove()//删除--------------------------------O(n)
minimum()//最小节点
maximum()//最大节点
predecessor()//前驱
successor()//后继

查找和插入实现比较简单

下面看删除操作：
(1)如果被删除节点至多有不超过一个儿子节点，则只要将儿子节点代替它而链接到它原来的位置即可
(2)否则的话需要先删除这个节点的后继（此时这个后继一定存在与它的右子树中且后继最多只有一个儿子节点）
然后用后继的值覆盖它即可.