二叉查找树是二叉树的一个特化,它具有的特殊性质是:对于树中的任何一个结点,它的左子树的所有结点的关键字都小于此结点的关键字,而右子树的所有结点的关键字都大于此结点的关键字.
二叉查找树的这种特殊性质使得它在查找元素的时候特别的方便,每一次查找都可以去掉一半的元素,因此查找的时间是O(logN).
二叉查找树的插入和查找算法也是很简单的,就是与当前结点的关键字作比较决定在右边还是左边继续操作.
二叉查找树最复杂的算法就是删除结点的算法了,根据所要删除的结点有两个子结点还是只有一个或者没有子结点会有不同的处理.有两个子结点的情况一般的处理是找到右子树中值最小的一个结点,将它的值替代当前的结点值,然后再把这个值最小的结点删除,也就是说有两个子结点的情况是用最小的一个大于当前结点关键字的结点替代了当前的结点(很拗口,但愿我说清楚了:)在只有一个或者没有子结点的情况就比较的简单了,如果还有子结点就把子结点的位置往上挪,然后把当前结点删除.
实现如下:
1)BSTree.h
/**//********************************************************************
created: 2006/07/28
filename: BSTree.h
author: 李创
http://www.cppblog.com/converse/
purpose: 二叉查找树的实现代码
*********************************************************************/
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include <stdio.h>
template<typename T>
struct BTreeNode
{
T Data;
BTreeNode* pLeft;
BTreeNode* pRight;
BTreeNode* pParent;
BTreeNode( T data = T(), BTreeNode<T>* Parent = NULL,
BTreeNode<T>* Left = NULL, BTreeNode<T>* Right = NULL)
: Data(data), pLeft(Left), pRight(Right), pParent(Parent)
{
}
};
template<typename T>
class BSTree
{
protected:
BTreeNode<T>* m_pRootNode;
public:
BSTree(BTreeNode<T>* pRoot = NULL)
: m_pRootNode(pRoot)
{
}
~BSTree();
void Display();
BTreeNode<T>* Insert(const T& data);
BTreeNode<T>* Find(const T& data);
BTreeNode<T>* FindMin();
BTreeNode<T>* FindMax();
BTreeNode<T>* Delete(const T& data);
private:
void Display(BTreeNode<T>* p);
BTreeNode<T>* Insert(const T& data, BTreeNode<T>* p);
BTreeNode<T>* Find(const T& data, BTreeNode<T>* p);
BTreeNode<T>* FindMin(BTreeNode<T>* p);
BTreeNode<T>* FindMax(BTreeNode<T>* p);
BTreeNode<T>* Delete(const T& data, BTreeNode<T>* p);
void DestructImpl(BTreeNode<T>* p);
};
#endif
2)BSTree.cpp
/**//********************************************************************
created: 2006/07/28
filename: BSTree.cpp
author: 李创
http://www.cppblog.com/converse/
purpose: 二叉查找树的实现代码
*********************************************************************/
#include <iostream>
#include "BSTree.h"
template<typename T>
BSTree<T>::~BSTree()
{
DestructImpl(m_pRootNode);
}
template<typename T>
void BSTree<T>::DestructImpl(BTreeNode<T>* p)
{
if (NULL == p)
return;
DestructImpl(p->pLeft);
DestructImpl(p->pRight);
p->pLeft = NULL;
p->pRight = NULL;
p->pParent = NULL;
delete p;
p = NULL;
}
template<typename T>
void BSTree<T>::Display()
{
Display(m_pRootNode);
}
// 中序打印出树中的元素,这样应该是从小到大的顺序
template<typename T>
void BSTree<T>::Display(BTreeNode<T>* p)
{
if (NULL == p)
return;
Display(p->pLeft);
std::cout << "Node = " << p->Data << std::endl;
Display(p->pRight);
}
template<typename T>
BTreeNode<T>* BSTree<T>::Insert(const T& data)
{
return Insert(data, m_pRootNode);
}
template<typename T>
BTreeNode<T>* BSTree<T>::Insert(const T& data, BTreeNode<T>* p)
{
if (NULL == p)
{
p = new BTreeNode<T>(data);
if (NULL == p)
{
return NULL;
}
else if (NULL == m_pRootNode)
{
m_pRootNode = p;
}
}
else if (data > p->Data)
{
p->pRight = Insert(data, p->pRight);
if (NULL != p->pRight)
{
p->pRight->pParent = p;
}
}
else
{
p->pLeft = Insert(data, p->pLeft);
if (NULL != p->pLeft)
{
p->pLeft->pParent = p;
}
}
return p;
}
template<typename T>
BTreeNode<T>* BSTree<T>::Find(const T& data)
{
return Find(data, m_pRootNode);
}
template<typename T>
BTreeNode<T>* BSTree<T>::Find(const T& data, BTreeNode<T>* p)
{
if (NULL == p)
{
return NULL;
}
else
{
if (data == p->Data)
{
return p;
}
else if (data > p->Data)
{
return Find(data, p->pRight);
}
else
{
return Find(data, p->pLeft);
}
}
}
template<typename T>
BTreeNode<T>* BSTree<T>::FindMin()
{
return FindMin(m_pRootNode);
}
template<typename T>
BTreeNode<T>* BSTree<T>::FindMin(BTreeNode<T>* p)
{
if (NULL == p)
{
return NULL;
}
if (NULL != p->pLeft)
{
return FindMin(p->pLeft);
}
else
{
return p;
}
}
template<typename T>
BTreeNode<T>* BSTree<T>::FindMax()
{
return FindMax(m_pRootNode);
}
template<typename T>
BTreeNode<T>* BSTree<T>::FindMax(BTreeNode<T>* p)
{
if (NULL == p)
{
return NULL;
}
if (NULL != p->pRight)
{
return FindMax(p->pRight);
}
else
{
return p;
}
}
template<typename T>
BTreeNode<T>* BSTree<T>::Delete(const T& data)
{
return Delete(data, m_pRootNode);
}
template<typename T>
BTreeNode<T>* BSTree<T>::Delete(const T& data, BTreeNode<T>* p)
{
if (NULL == p)
{
return NULL;
}
else if (data < p->Data)
{
p->pLeft = Delete(data, p->pLeft);
}
else if (data > p->Data)
{
p->pRight = Delete(data, p->pRight);
}
else if (NULL != p->pLeft && NULL != p->pRight)
{
// 找到结点且有两个子结点
BTreeNode<T>* pNode;
// 找到右子树中最小的结点,把它的值替换当前结点值,然后删除找到的那个结点
pNode = FindMin(p->pRight);
p->Data = pNode->Data;
p->pRight = Delete(p->Data, p->pRight);
}
else
{
// 找到结点但是只有一个或没有子结点
// 如果有子结点就用子结点代替当前结点,然后删除当前结点
BTreeNode<T>* pNode = p;
if (NULL == p->pLeft)
{
p = p->pRight;
}
else if (NULL == p->pRight)
{
p = p->pLeft;
}
delete pNode;
pNode = NULL;
}
return p;
}
3)Main.cpp
#include "BSTree.h"
#include <stdlib.h>
#include <time.h>
// 创建一个数组,元素值随机设置
void CreateNewArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
array[i] = rand() % 256;
}
}
int main()
{
int array[10];
srand(time(NULL));
CreateNewArray(array, 10);
BSTree<int> tree;
for (int i = 0; i < 10; ++i)
{
tree.Insert(array[i]);
}
tree.Display();
if (NULL != tree.Find(array[7]))
{
std::cout << "Find!\n";
}
BTreeNode<int>* pNode;
if (NULL != (pNode = tree.FindMin()))
{
std::cout << "Min = " << pNode->Data << std::endl;
}
if (NULL != (pNode = tree.FindMax()))
{
std::cout << "Max = " << pNode->Data << std::endl;
}
tree.Delete(array[7]);
std::cout << "\nafter delete " << array[7] << std::endl;
tree.Display();
system("pause");
return 0;
} 需要说明一点:上面做测试用的Main.cpp如果单独写在一个文件中就会在链接的时候报错,报的错误是:
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Insert(int const &)" (
?Insert@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: __thiscall BSTree<int>::~BSTree<int>(void)" (
??1?$BSTree@H@@QAE@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Delete(int const &)" (
?Delete@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMax(void)" (
?FindMax@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMin(void)" (
?FindMin@?$BSTree@H@@QAEPAU?$BTreeNode@H@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Find(int const &)" (
?Find@?$BSTree@H@@QAEPAU?$BTreeNode@H@@ABH@Z) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: void __thiscall BSTree<int>::Display(void)" (
?Display@?$BSTree@H@@QAEXXZ) referenced in function _main
所以没有办法,我只能将main.cpp中的内容copy到BSTree.cpp中才能链接过去.
如果哪位朋友知道如何解决上面因为采用了模板类出现的链接错误,我不胜感激,谢谢!