1、二叉搜索树

(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)插入函数：

重分利用搜索二叉树的性质：

voidinsert(BSTreeNode<Type>*&t,constType&x){if(t==NULL){t=newBSTreeNode<Type>(x);return;}elseif(x<t->data){insert(t->leftChild,x);}elseif(x>t->data){insert(t->rightChild,x);}else{return;}}

(4)、删除函数：

思想：要删除一个有左孩子或右孩子或是叶子结点，看成一种情况，做法：保存要删除的结点,因为传的是引用，可以直接修改上一个结点的左孩子或右孩子，使其跨过当前的直指下一个结点，在释放当前的结点空间。

第二种情况：就是要删除的既有左子树，又有右子树，此时可以有两种做法：i>找左子树最大的数字，覆盖要删除的数字，在往左子树找这个数字删除-->递归！ii>找右子树最小的数字，覆盖要删除的数字，在往右子树找这个数字删除-->递归！

第一种情况图形想法如下：

删除左边和删除右边，还有是叶子结点，想法一样。

第二种情况图形想法如下：

代码如下：

boolremove(BSTreeNode<Type>*&t,constType&key){if(t==NULL){//t传的是引用，每次可以进行直接更改!returnfalse;}if(key<t->data){remove(t->leftChild,key);}elseif(key>t->data){remove(t->rightChild,key);}else{if(t->leftChild!=NULL&&t->rightChild!=NULL){//第二种情况BSTreeNode<Type>*p=t->rightChild;while(p->leftChild!=NULL){p=p->leftChild;}t->data=p->data;remove(t->rightChild,p->data);//在右树找p->data的数字进行删除;}else{//第一种情况BSTreeNode<Type>*p=t;if(t->leftChild==NULL){t=t->rightChild;//引用的好处体现出来了;}else{t=t->leftChild;//引用的好处体现出来了;}deletep;}}returntrue;}/*以下这个代码是先想到的，比较容易，上面这个是经过思考的，将三种情况看成一种情况来处理。boolremove(BSTreeNode<Type>*&t,constType&key){if(t==NULL){returnfalse;}if(key<t->data){remove(t->leftChild,key);}elseif(key>t->data){remove(t->rightChild,key);}else{//以下三种情况可以看成一种；if(t->leftChild==NULL&&t->rightChild==NULL){deletet;t=NULL;}elseif(t->leftChild!=NULL&&t->rightChild==NULL){BSTreeNode<Type>*p=t;t=t->leftChild;deletep;}elseif(t->leftChild==NULL&&t->rightChild!=NULL){BSTreeNode<Type>*p=t;t=t->rightChild;deletep;}else{BSTreeNode<Type>*p=t->rightChild;while(p->leftChild!=NULL){p=p->leftChild;}t->data=p->data;remove(t->rightChild,p->data);}}returntrue;}*/

4、搜索二叉树的完整代码、测试代码、测试结果

(1)、完整代码：

#ifndef_BSTREE_H_#define_BSTREE_H_#include<iostream>usingnamespacestd;#defineMIN_NUMBER-8937589#defineMAX_NUMBER99999999template<typenameType>classBSTree;template<typenameType>classBSTreeNode{friendclassBSTree<Type>;public:BSTreeNode():data(Type()),leftChild(NULL),rightChild(NULL){}BSTreeNode(Typed,BSTreeNode*left=NULL,BSTreeNode*right=NULL):data(d),leftChild(left),rightChild(right){}~BSTreeNode(){}private:Typedata;BSTreeNode*leftChild;BSTreeNode*rightChild;};template<typenameType>classBSTree{public:BSTree():root(NULL){}BSTree<Type>&operator=(constBSTree&bst){if(this!=&bst){root=copy(bst.root);}return*this;}~BSTree(){}public:voidinsert(constType&x){insert(root,x);}voidinOrder()const{inOrder(root);}TypeMin()const{returnMin(root);}TypeMax()const{returnMax(root);}BSTreeNode<Type>*find(constType&key)const{returnfind(root,key);}BSTreeNode<Type>*copy(constBSTreeNode<Type>*t){if(t==NULL){returnNULL;}BSTreeNode<Type>*tmp=newBSTreeNode<Type>(t->data);tmp->leftChild=copy(t->leftChild);tmp->rightChild=copy(t->rightChild);returntmp;}BSTreeNode<Type>*parent(constType&key)const{returnparent(root,key);}boolremove(constType&key){returnremove(root,key);}protected:boolremove(BSTreeNode<Type>*&t,constType&key){if(t==NULL){//重点：传的是引用returnfalse;}if(key<t->data){remove(t->leftChild,key);}elseif(key>t->data){remove(t->rightChild,key);}else{if(t->leftChild!=NULL&&t->rightChild!=NULL){BSTreeNode<Type>*p=t->rightChild;while(p->leftChild!=NULL){p=p->leftChild;}t->data=p->data;remove(t->rightChild,p->data);}else{BSTreeNode<Type>*p=t;if(t->leftChild==NULL){t=t->rightChild;//可以直接更改左右孩子}else{t=t->leftChild;//可以直接更改左右孩子}deletep;}}returntrue;}/*boolremove(BSTreeNode<Type>*&t,constType&key){if(t==NULL){returnfalse;}if(key<t->data){remove(t->leftChild,key);}elseif(key>t->data){remove(t->rightChild,key);}else{//以下三种情况可以看成一种；if(t->leftChild==NULL&&t->rightChild==NULL){deletet;t=NULL;}elseif(t->leftChild!=NULL&&t->rightChild==NULL){BSTreeNode<Type>*p=t;t=t->leftChild;deletep;}elseif(t->leftChild==NULL&&t->rightChild!=NULL){BSTreeNode<Type>*p=t;t=t->rightChild;deletep;}else{BSTreeNode<Type>*p=t->rightChild;while(p->leftChild!=NULL){p=p->leftChild;}t->data=p->data;remove(t->rightChild,p->data);}}returntrue;}*/BSTreeNode<Type>*parent(BSTreeNode<Type>*t,constType&key)const{if(t==NULL||t->data==key){returnNULL;}if(t->leftChild->data==key||t->rightChild->data==key){returnt;}if(key<t->data){returnparent(t->leftChild,key);}else{returnparent(t->rightChild,key);}}BSTreeNode<Type>*find(BSTreeNode<Type>*t,constType&key)const{if(t==NULL){returnNULL;}if(t->data==key){returnt;}elseif(key<t->data){returnfind(t->leftChild,key);}else{returnfind(t->rightChild,key);}}TypeMax(BSTreeNode<Type>*t)const{if(t!=NULL){while(t->rightChild){t=t->rightChild;}returnt->data;}returnMAX_NUMBER;}TypeMin(BSTreeNode<Type>*t)const{if(t!=NULL){while(t->leftChild){t=t->leftChild;}returnt->data;}returnMIN_NUMBER;}voidinOrder(BSTreeNode<Type>*t)const{if(t!=NULL){inOrder(t->leftChild);cout<<t->data<<"";inOrder(t->rightChild);}}voidinsert(BSTreeNode<Type>*&t,constType&x){if(t==NULL){t=newBSTreeNode<Type>(x);return;}elseif(x<t->data){insert(t->leftChild,x);}elseif(x>t->data){insert(t->rightChild,x);}else{return;}}private:BSTreeNode<Type>*root;};#endif

(2)测试代码：

#include"bstree.h"intmain(void){intar[]={3,7,9,1,0,6,4,2,};intn=sizeof(ar)/sizeof(int);BSTree<int>bst;for(inti=0;i<n;i++){bst.insert(ar[i]);}bst.inOrder();cout<<endl;cout<<bst.Min()<<endl;cout<<bst.Max()<<endl;BSTreeNode<int>*p=bst.find(6);BSTreeNode<int>*q=bst.parent(4);printf("%p%p\n",p,q);bst.remove(0);bst.inOrder();cout<<endl;return0;}

(3)、测试结果：