数据结构-二叉查找树（BST）

   二叉查找树是一种比较特殊的二叉树，表现为任意节点的值都比左孩子的值要大，而且小于等于右孩子的值，采用中序遍历BST（Binary Search Tree）就可以的到排序好的元素集合，而且插入删除的时间消耗也比较合理，但是有一个缺点就是内存开销有点大，下面简单介绍BST。

下面就是两棵二叉查找树

BST实现主要采用递归来实现，所以在学习实现的过程中也可以加深对递归的理解和掌握。具体代码的意思在注释中均有明确的说明，下面看具体的实现

首先是定义一个节点的类Node，文件名为”Node.h“，由于存储的参数类型具体不了解，所以此处采用了模板的实现方法，实现了节点的一些常用操作。

#ifndef NODE_H
#define NODE_H

/*
 *二叉树节点Node，实现了一些简单地节点操作，
 *比如，获取左右子节点，修改左右子节点等，
 *含有三个参数
 *由于节点元素数据类型未知，故采用模板实现
 */

template
class Node{
private:
//节点的元素值
Elem value;
//节点的左指针
Node * leftPtr;
//节点的右指针
Node * rightPtr;

public:
Node(Elem e, Node * lp = NULL, Node * rp = NULL){
value = e;
leftPtr = lp;
rightPtr = rp;
}

//判断是否为叶子节点
bool isLeaf() const{
return (leftPtr == NULL && rightPtr == NULL);
}

//获取节点的value值
Elem getValue() const{
return value;
}

//修改节点的value值
void setValue(Elem e){
value = e;
}

//获取左节点指针
Node * getLeft() const{
return leftPtr;
}

//设置左子节点
void setLeft(Node * left){
leftPtr = left;
}

//获取右节点指针
Node * getRight() const{
return rightPtr;
}

//设置右节点
void setRight(Node * right){
rightPtr = right;
}
};
#endif

有了节点之后，我们就可以考虑具体的BST实现了

#ifndef BST_H
#define BST_H

#include
#include
#include"Node.h"

using namespace std;

template
class BST{

public:
BST(){
rootNode = NULL;
nodeCount = 0;
}

~BST(){
delete[] rootNode;
}

//插入一个元素e
bool insert(const Elem& e){
rootNode = insertHelp(rootNode, e);
++nodeCount;
return true;
}

//移除一个元素e
bool remove(const Elem & e){
//mark标记删除元素是否在BST中
Node * mark = NULL;
rootNode = removeHelp(rootNode, e, mark);
if (mark == NULL){
cout <<"Error: 所要删除的元素 " <return false;
}
else{
nodeCount--;
delete [] mark;
return true;
}
}

//中序遍历打印BST
void show(){
showHelper(rootNode);
cout <}

private:
//指向整个BST的指针
Node * rootNode;
//BST节点个数
int nodeCount;

//实现在bst中正确位置插入元素
Node * insertHelp(Node * subroot, const Elem & e){
//当递归到空位置时，即找到了合适的插入位置，
//此时返回一个新节点作为上次递归调用subroot的孩子节点
if (subroot == NULL){
return new Node(e);
}
//当前节点值大于要插入值时，说明插入位置在当前位置的左边，递归调用
if (subroot->getValue() > e){
subroot->setLeft(insertHelp(subroot->getLeft(), e));
}
//当前节点值小于要插入值时，说明插入位置在当前位置的右边，递归调用
else{
subroot->setRight(insertHelp(subroot->getRight(), e));
}
return subroot;
}

//删除最小值，返回删除后的树的根节点指针
Node * deleteMin(Node * subroot, Node * & min){
//当左节点为空时，表示已经找到最小元素，此时把最小元素赋值min
if (subroot->getLeft() == NULL){
min = subroot;
return subroot->getRight();
}
else{  //当左节点不是空节点的时候，递归调用
subroot->setLeft(deleteMin(subroot->getLeft(), min));
return subroot;
}
}


//删除操作的帮助实现函数
//当元素e不在树中是mark值为NULL，当e在树中时，mark值为e元素对应的节点指针
Node * removeHelp(Node * subroot, const Elem e, Node * & mark){
//当subroot为NULL时表示找不到删除元素对应节点
if (subroot == NULL){
return NULL;
}

//当前元素值大于要删除的元素值，表示删除当前元素在元素的左边
else if (subroot->getValue() > e){
subroot->setLeft(removeHelp(subroot->getLeft(), e, mark));
}

//当前元素值小于要删除的元素值，表示删除当前元素在元素的右边
else if (subroot->getValue() subroot->setRight(removeHelp(subroot->getRight(), e, mark));
}

//找到删除元素对应节点
else{
//删除节点左孩子为空
//标记mark，表示找到删除元素
//直接让subroot指针指向subroot的右子节点
if (subroot->getLeft() == NULL){
mark = subroot;
subroot = subroot->getRight();
}
//删除节点右孩子为空
//标记mark，表示找到删除元素
//直接让subroot指针指向subroot的左子节点
else if (subroot->getRight() == NULL){
mark = subroot;
subroot = subroot->getLeft();
}
//删除两个子节点均不为空
else{
//删除subroot右子树最小节点temp，然后把subroot值赋为temp的值
//标记mark，表示找到删除元素
Node * temp;
subroot->setRight(deleteMin(subroot->getRight(), temp));
Elem te = subroot->getValue();
subroot->setValue(temp->getValue());
temp->setValue(te);
mark = temp;
}
}
return subroot;
}

//中序遍历BST
Node * showHelper(Node * subroot){
if (subroot == NULL){
return NULL;
}
showHelper(subroot->getLeft());
cout <getValue();
showHelper(subroot->getRight());
}

};
#endif

上面的程序实现了BST基本的功能，下面就来简单总结一下BST的特点吧。

  在BST中，insert，remove，find操作的时间消耗平均都是(log n)，但在最坏情况下都是（n），所以说保持树的平衡是很重要的，就是保持节点左右两边元素个数基本相同。