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)插入函数:
重分利用搜索二叉树的性质:
void insert(BSTreeNode<Type> *&t, const Type &x){ if(t == NULL){ t = new BSTreeNode<Type>(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<Type> *&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<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; //引用的好处体现出来了; } delete p; } } return true; } /* 以下这个代码是先想到的,比较容易,上面这个是经过思考的,将三种情况看成一种情况来处理。 bool remove(BSTreeNode<Type> *&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<Type> *p = t; t = t->leftChild; delete p; }else if(t->leftChild == NULL && t->rightChild != NULL){ BSTreeNode<Type> *p = t; t = t->rightChild; delete p; }else{ BSTreeNode<Type> *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<iostream> using namespace std; #define MIN_NUMBER -8937589 #define MAX_NUMBER 99999999 template<typename Type> class BSTree; template<typename Type> class BSTreeNode{ friend class BSTree<Type>; 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<typename Type> class BSTree{ public: BSTree() : root(NULL){} BSTree<Type>& 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<Type>* find(const Type &key)const{ return find(root, key); } BSTreeNode<Type> *copy(const BSTreeNode<Type> *t){ if(t == NULL){ return NULL; } BSTreeNode<Type> *tmp = new BSTreeNode<Type>(t->data); tmp->leftChild = copy(t->leftChild); tmp->rightChild = copy(t->rightChild); return tmp; } BSTreeNode<Type>* parent(const Type &key)const{ return parent(root, key); } bool remove(const Type &key){ return remove(root, key); } protected: bool remove(BSTreeNode<Type> *&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<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; //可以直接更改左右孩子 } delete p; } } return true; } /* bool remove(BSTreeNode<Type> *&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<Type> *p = t; t = t->leftChild; delete p; }else if(t->leftChild == NULL && t->rightChild != NULL){ BSTreeNode<Type> *p = t; t = t->rightChild; delete p; }else{ BSTreeNode<Type> *p = t->rightChild; while(p->leftChild != NULL){ p = p->leftChild; } t->data = p->data; remove(t->rightChild, p->data); } } return true; }*/ BSTreeNode<Type>* parent(BSTreeNode<Type> *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<Type>* find(BSTreeNode<Type> *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<Type> *t)const{ if(t != NULL){ while(t->rightChild){ t = t->rightChild; } return t->data; } return MAX_NUMBER; } Type Min(BSTreeNode<Type> *t)const{ if(t != NULL){ while(t->leftChild){ t = t->leftChild; } return t->data; } return MIN_NUMBER; } void inOrder(BSTreeNode<Type> *t)const{ if(t != NULL){ inOrder(t->leftChild); cout<<t->data<<" "; inOrder(t->rightChild); } } void insert(BSTreeNode<Type> *&t, const Type &x){ if(t == NULL){ t = new BSTreeNode<Type>(x); return; }else if(x < t->data){ insert(t->leftChild, x); }else if(x > t->data){ insert(t->rightChild, x); }else{ return; } } private: BSTreeNode<Type> *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<int> bst; for(int i = 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; return 0; }
(3)、测试结果:
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。