1、二叉搜索树
创新互联建站-专业网站定制、快速模板网站建设、高性价比墨江网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式墨江网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖墨江地区。费用合理售后完善，10余年实体公司更值得信赖。
(1)、逼近折半查找的查找算法；
(2)、一般不允许出现重复数字，不然没法存储；
(3)、满足：左孩子数据 < 根结点数据 < 右孩子数据；根(父)结点比左孩子的大，比右孩子的小；
(4)左子树和右子树也是二叉搜索树；
2、为什么叫二叉搜索树？
如果对一颗二叉搜索树进行中序遍历，可以按从小到大的顺序输出，此时又叫做二叉排序树。
如图：
3、搜索二叉树上的操作
全部用C++实现的。
(1)、之前学习二叉树，并没有说什么插入，删除操作，那是因为，没有规律而言，怎么进行操作呢？搜索二叉树的规律如此明显，那么插入，删除必是重中之中！
(2)、我们输入相同的数字，但是顺序不同的话，生成的搜索二叉树是不一样的！
例：int ar[] = {3, 7, 9, 1, 0, 6, 4, 2,}; 和int ar[] = {7, 3, 9, 1, 0, 6, 4, 2,}; 生成的搜索二叉树不一样。
(3)插入函数：
重分利用搜索二叉树的性质：
void insert(BSTreeNode *&t, const Type &x){
if(t == NULL){
t = new BSTreeNode(x);
return;
}else if(x < t->data){
insert(t->leftChild, x);
}else if(x > t->data){
insert(t->rightChild, x);
}else{
return;
}
}
(4)、删除函数：
思想：要删除一个有左孩子或右孩子或是叶子结点，看成一种情况，做法：保存要删除的结点,因为传的是引用，可以直接修改上一个结点的左孩子或右孩子，使其跨过当前的直指下一个结点，在释放当前的结点空间。
第二种情况：就是要删除的既有左子树，又有右子树，此时可以有两种做法：i>找左子树最大的数字，覆盖要删除的数字，在往左子树找这个数字删除-->递归！ii>找右子树最小的数字，覆盖要删除的数字，在往右子树找这个数字删除-->递归！
第一种情况图形想法如下：
删除左边和删除右边，还有是叶子结点，想法一样。
第二种情况图形想法如下：
代码如下：
bool remove(BSTreeNode *&t, const Type &key){
if(t == NULL){ //t传的是引用，每次可以进行直接更改!
return false;
}
if(key < t->data){
remove(t->leftChild, key);
}else if(key > t->data){
remove(t->rightChild, key);
}else{
if(t->leftChild != NULL && t->rightChild != NULL){ //第二种情况
BSTreeNode *p = t->rightChild;
while(p->leftChild != NULL){
p = p->leftChild;
}
t->data = p->data;
remove(t->rightChild, p->data); //在右树找p->data的数字进行删除;
}else{ //第一种情况
BSTreeNode *p = t;
if(t->leftChild == NULL){
t = t->rightChild; //引用的好处体现出来了;
}else{
t = t->leftChild; //引用的好处体现出来了;
}
delete p;
}
}
return true;
}
/* 以下这个代码是先想到的，比较容易，上面这个是经过思考的，将三种情况看成一种情况来处理。
bool remove(BSTreeNode *&t, const Type &key){
if(t == NULL){
return false;
}
if(key < t->data){
remove(t->leftChild, key);
}else if(key > t->data){
remove(t->rightChild, key);
}else{ //以下三种情况可以看成一种；
if(t->leftChild == NULL && t->rightChild == NULL){
delete t;
t = NULL;
}else if(t->leftChild != NULL && t->rightChild == NULL){
BSTreeNode *p = t;
t = t->leftChild;
delete p;
}else if(t->leftChild == NULL && t->rightChild != NULL){
BSTreeNode *p = t;
t = t->rightChild;
delete p;
}else{
BSTreeNode *p = t->rightChild;
while(p->leftChild != NULL){
p = p->leftChild;
}
t->data = p->data;
remove(t->rightChild, p->data);
}
}
return true;
}
*/
4、搜索二叉树的完整代码、测试代码、测试结果
(1)、完整代码：
#ifndef _BSTREE_H_
#define _BSTREE_H_
#include
using namespace std;
#define MIN_NUMBER -8937589
#define MAX_NUMBER 99999999
template
class BSTree;
template
class BSTreeNode{
friend class BSTree;
public:
BSTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}
BSTreeNode(Type d, BSTreeNode *left = NULL, BSTreeNode *right = NULL)
: data(d), leftChild(left), rightChild(right){}
~BSTreeNode(){}
private:
Type data;
BSTreeNode *leftChild;
BSTreeNode *rightChild;
};
template
class BSTree{
public:
BSTree() : root(NULL){}
BSTree& operator=(const BSTree &bst){
if(this != &bst){
root = copy(bst.root);
}
return *this;
}
~BSTree(){}
public:
void insert(const Type &x){
insert(root, x);
}
void inOrder()const{
inOrder(root);
}
Type Min()const{
return Min(root);
}
Type Max()const{
return Max(root);
}
BSTreeNode* find(const Type &key)const{
return find(root, key);
}
BSTreeNode *copy(const BSTreeNode *t){
if(t == NULL){
return NULL;
}
BSTreeNode *tmp = new BSTreeNode(t->data);
tmp->leftChild = copy(t->leftChild);
tmp->rightChild = copy(t->rightChild);
return tmp;
}
BSTreeNode* parent(const Type &key)const{
return parent(root, key);
}
bool remove(const Type &key){
return remove(root, key);
}
protected:
bool remove(BSTreeNode *&t, const Type &key){
if(t == NULL){ //重点：传的是引用
return false;
}
if(key < t->data){
remove(t->leftChild, key);
}else if(key > t->data){
remove(t->rightChild, key);
}else{
if(t->leftChild != NULL && t->rightChild != NULL){
BSTreeNode *p = t->rightChild;
while(p->leftChild != NULL){
p = p->leftChild;
}
t->data = p->data;
remove(t->rightChild, p->data);
}else{
BSTreeNode *p = t;
if(t->leftChild == NULL){
t = t->rightChild; //可以直接更改左右孩子
}else{
t = t->leftChild; //可以直接更改左右孩子
}
delete p;
}
}
return true;
}
/*
bool remove(BSTreeNode *&t, const Type &key){
if(t == NULL){
return false;
}
if(key < t->data){
remove(t->leftChild, key);
}else if(key > t->data){
remove(t->rightChild, key);
}else{ //以下三种情况可以看成一种；
if(t->leftChild == NULL && t->rightChild == NULL){
delete t;
t = NULL;
}else if(t->leftChild != NULL && t->rightChild == NULL){
BSTreeNode *p = t;
t = t->leftChild;
delete p;
}else if(t->leftChild == NULL && t->rightChild != NULL){
BSTreeNode *p = t;
t = t->rightChild;
delete p;
}else{
BSTreeNode *p = t->rightChild;
while(p->leftChild != NULL){
p = p->leftChild;
}
t->data = p->data;
remove(t->rightChild, p->data);
}
}
return true;
}*/
BSTreeNode* parent(BSTreeNode *t, const Type &key)const{
if(t == NULL || t->data == key){
return NULL;
}
if(t->leftChild->data == key || t->rightChild->data == key){
return t;
}
if(key < t->data){
return parent(t->leftChild, key);
}else{
return parent(t->rightChild, key);
}
}
BSTreeNode* find(BSTreeNode *t, const Type &key)const{
if(t == NULL){
return NULL;
}
if(t->data == key){
return t;
}else if(key < t->data){
return find(t->leftChild, key);
}else{
return find(t->rightChild, key);
}
}
Type Max(BSTreeNode *t)const{
if(t != NULL){
while(t->rightChild){
t = t->rightChild;
}
return t->data;
}
return MAX_NUMBER;
}
Type Min(BSTreeNode *t)const{
if(t != NULL){
while(t->leftChild){
t = t->leftChild;
}
return t->data;
}
return MIN_NUMBER;
}
void inOrder(BSTreeNode *t)const{
if(t != NULL){
inOrder(t->leftChild);
cout<data<<" ";
inOrder(t->rightChild);
}
}
void insert(BSTreeNode *&t, const Type &x){
if(t == NULL){
t = new BSTreeNode(x);
return;
}else if(x < t->data){
insert(t->leftChild, x);
}else if(x > t->data){
insert(t->rightChild, x);
}else{
return;
}
}
private:
BSTreeNode *root;
};
#endif
(2)测试代码：
#include"bstree.h"
int main(void){
int ar[] = {3, 7, 9, 1, 0, 6, 4, 2,};
int n = sizeof(ar) / sizeof(int);
BSTree bst;
for(int i = 0; i < n; i++){
bst.insert(ar[i]);
}
bst.inOrder();
cout< *p = bst.find(6);
BSTreeNode *q = bst.parent(4);
printf("%p %p\n", p, q);
bst.remove(0);
bst.inOrder();
cout< (3)、测试结果：
当前文章：BST二叉搜索树
文章来源：http://cdxtjz.cn/article/peiccc.html
