二叉查找树是二叉树的一个特化,它具有的特殊性质是:对于树中的任何一个结点,它的左子树的所有结点的关键字都小于此结点的关键字,而右子树的所有结点的关键字都大于此结点的关键字.
二叉查找树的这种特殊性质使得它在查找元素的时候特别的方便,每一次查找都可以去掉一半的元素,因此查找的时间是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