一个二叉搜索树的C++实现
时间：2010-10-23 来源：sld666666
文章是对代码的解释， 源码的贴出放在最后。
在阅读本片代码的时候注意一下几点：
# 用了泛型技术：templeate <class T>
# const 引用 （C++程序员装B必备）
在阅读代码的时候可能会不太习惯。
1. 二叉搜索树的结构
一个二叉树的如果不为空便是由一个根节点和左右两个只树构成。
二叉搜索树可以提供对数时间的插入和访问，其节点的放置规则是：任何一个节点的键值一定大于其左树节点的键值，而且小于其右树节点的值。
我们可以定义如下的节点：
template <class T>
struct BinaryNode
{
T element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const T& theElement,
BinaryNode *lt,
BinaryNode *rt):
element(theElement),
left(lt),
right(rt)
{
}
};
element 表示节点的键值；
left 表示指向左树节点的指针
right表示指向右树节点的指针
1. 二叉搜索树类的属性、方法
在这里， 这个树类提供了如下几个方法： findMin();findMax();contains():makeEmpty();insert():remove():printTree(): 我们可以先来看下这个类的定义：
template <class T>
class BinarySearchTree
{
private:
BinaryNode<T> *m_root;
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree& rhs);
~BinarySearchTree();
const T& findMin() const;
const T& findMax() const;
bool contains(const T& x) const;
void printTree(ORDER_MODE eOrderMode = ORDER_MODE_PREV) const;
void makeEmpty();
void insert(const T& x);
void remove(const T& x);
private:
//因为树的方法用到了很多递归， 所以这里我们需要申明如下的私有成员函数
void insert(const T& x, BinaryNode<T>* &t) ;
void remove(const T& x, BinaryNode<T>* &t) ;
BinaryNode<T>* findMin( BinaryNode<T>* t) const;
BinaryNode<T>* findMax( BinaryNode<T>* t) const;
bool contains(const T& x, const BinaryNode<T>* t) const;
void makeEmpty(BinaryNode<T>* t);
void printTreeInPrev(BinaryNode<T>* t) const;
void printTreeInMid(BinaryNode<T>* t)const;
void printTreeInPost(BinaryNode<T>* t)const;
};
这里解释下为什么要重载这么多私有的成员函数。因为树的方法用到了很多递归， 所以这里我们需要重载这些私有成员函数，当我们写代码的时候，我们便可以这样做：
template <class T>
bool BinarySearchTree<T>::contains(const T& x) const
{
return contains(x, m_root);
}
template <class T>
bool BinarySearchTree<T>::contains(const T& x, const BinaryNode<T>* t) const
{
这里调用自己
}
下面解释各个方法的具体实现。
2.BinarySearchTree的构造、析构以及拷贝构造函数
类BinarySearchTree的构造、析构以及拷贝构造函数没什么特殊的地方。实现如下：
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
m_root = NULL;
}
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
m_root = rhs.m_root;
}
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
makeEmpty();
}
2. BinarySearchTree::contains(X)
此方法判断函数树是不是包含元素X. 可以看下具体实现：
// return true if the x is found in the tree
template <class T>
bool BinarySearchTree<T>::contains(const T& x) const
{
return contains(x, m_root);
}
template <class T>
bool BinarySearchTree<T>::contains(const T& x, const BinaryNode<T>* t) const
{
if (!t)
return false;
else if (x < t->element)
return contains(x, t->left);
else if (x > t->element)
return contains(x, t->right);
else
return true;
}
3. BinarySearchTree::makeEmpty()
清空这个树
template <class T>
void BinarySearchTree<T>::makeEmpty()
{
makeEmpty(m_root);
}
template <class T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
if (t)
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
实现非常简单，就是遍历整颗树，delete BinaryNode， 这里需要注意的一点是makeEmpty的参数是一个指针的引用：BinaryNode<T>* &t
4. BinarySearchTree::findMax() & BinarySearchTree::findMin()
findMax 和findMin的实现就是遍历树，比较相关的元素
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMax( BinaryNode<T>* t) const
{
//二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
if (t != NULL)
while (t->right != NULL)
t = t->right;
return t;
}
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMin( BinaryNode<T>* t) const
{
//二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
if (!t)
return NULL;
if (t->left == NULL)
return t;
else
return findMin(t->left);
}
5. BinarySearchTree的插入和删除
二叉树的插入比较简单， 只要循环得比较某一直，如果此值比根节点的值小，插入左子树，如果大插入右子树，如果相等，什么也不做
template <class T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
t = new BinaryNode<T>(x, NULL, NULL);//注意这个指针参数是引用
else if (x < t->element)
insert(x, t->left);
else if (x > t->element)
insert(x, t->right);
else
;//do nothing
}
二叉树的删除就比较复杂了，我们显得判断这个需要删除的节点有几个之节点，删除这个节点后其子节点引起的连锁反应。
template <class T>
void BinarySearchTree<T>::remove(const T& x, BinaryNode<T>* &t)
{
if (t == NULL)
return;
if (x < t->element)
remove(x, t->left);
else if (x > t->element)
remove (x, t->right);
else // now ==
{
if (t->left != NULL &&
t->right != NULL)//two child
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else
{
BinaryNode<T> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
}
这里实现的方法就是先拿出右树的最小值填充当前节点，以后节点依次干这件事情，然后删除最后的节点。
6. BinarySearchTree的遍历输出
二叉树的遍历有三种：前序，中序，后序。
前序遍历的规律是：输出根结点，输出左子树，输出右子树；
中序遍历的规律是：输出左子树，输出根结点，输出右子树；
后序遍历的规律是：输出左子树，输出右子树，输出根结点；
在这里我先定义了一个枚举来表示着三种类型的遍历方式：
enum ORDER_MODE
{
ORDER_MODE_PREV = 0,
ORDER_MODE_MID,
ORDER_MODE_POST
};
然后分别实现遍历：
//Print tree
template <class T>
void BinarySearchTree<T>::printTree(ORDER_MODE eOrderMode /*= ORDER_MODE_PREV*/) const
{
if (ORDER_MODE_PREV == eOrderMode)
printTreeInPrev(m_root);
else if (ORDER_MODE_MID == eOrderMode)
printTreeInMid(m_root);
else if (ORDER_MODE_POST == eOrderMode)
printTreeInPost(m_root);
else
;//do nothing
}
template <class T>
void BinarySearchTree<T>::printTreeInPrev(BinaryNode<T>* t) const
{
if (t)
{
cout << t->element;
printTreeInPrev(t->left);
printTreeInPrev(t->right);
}
}
template <class T>
void BinarySearchTree<T>::printTreeInMid(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPrev(t->left);
cout << t->element;
printTreeInPrev(t->right);
}
}
template <class T>
void BinarySearchTree<T>::printTreeInPost(BinaryNode<T>* t) const
{
if (t)
{
printTreeInPost(t->left);
printTreeInPost(t->right);
cout << t->element;
}
}
到此这个类的介绍，就完毕了， 下面可以敲下如下的测试代码：
#include "stdafx.h"
#include "BinarySearchTree.h"
int _tmain(int argc, _TCHAR* argv[])
{
BinarySearchTree<int> binaryTree;
binaryTree.insert(5);
binaryTree.insert(1);
binaryTree.insert(2);
binaryTree.insert(3);
binaryTree.insert(6);
binaryTree.insert(8);
bool b = binaryTree.contains(1);
int x = binaryTree.findMin();
cout << b << " "<< x <<endl;
x = binaryTree.findMax();
cout << x <<endl;
binaryTree.remove(2);
binaryTree.printTree(ORDER_MODE_PREV);
cout <<endl;
binaryTree.printTree(ORDER_MODE_MID);
cout <<endl;
binaryTree.printTree(ORDER_MODE_POST);
cout <<endl;
return 0;
}
结果为：
相关阅读 更多 +
