二叉搜索树
本章是为了C++的map和set做铺垫
概念与操作
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
二叉搜索树的插入
a. 树为空，则直接新增节点，赋值给root指针。
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点。
其实上面两个还是很容易实现的，最难的是删除这里，要考虑三种情况：
删除的是叶子结点，那就找到直接释放就好了。
删除的是只有一个左/右孩子的结点，那就先链接父亲结点和左/右孩子结点，然后直接删除该节点。
其实删除叶子结点可以和删除一个孩子结点的合并，因为叶子节点两个都是空，删除一个孩子的结点只有一个是空。
删除两个孩子结点的最麻烦，首先要找到替换这个结点的值，肯定是左子树最大的或者是右子树最小的。（二选一都可以，这里我选择左子树最小的）
性能分析
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：l o g 2 N log_2 Nlog2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N 2 \frac{N}{2}2N
其实二叉搜索树是一个不完整的树，遇到这种极端情况就没有办了，后面的AVL和红黑树会完成这个功能。
实现
实现这里我会写出某些成员函数的递归与迭代版本。
其实最难的是删除步骤：
如果是删除叶子结点直接删除就可以，只有一个孩子的就先看是只有左孩子还是只右有孩子，如果只有左孩子就让父节点的指针指向左孩子，如果只有右孩子就让父亲的指针指向右孩子，然后判断要删除的结点在父节点的左子树还是右子树，才能判断让父节点的左指针还是右指针去链接孩子。
但是这个思路还要考虑这种情况：
如果删除了根节点，那么就要换根。
如果是有两个孩子的就非常难办了，首先要去替换，这里用左子树的最小节点去替换。
先来看看第一种情况：
删除3，首先让3和左子树的最小值4交换（赋值也行），然后让cur记住原来是3这里，再来一个指针记录原来是4这里，再用parent指向父节点6的位置：
然后删除minright之前，将parent的左指针指向minright的右指针，因为minright左指针肯定是没有值了，但是右指针不一定没有。
然后是第二种情况：
删除的是根，这里只能和10交换，parent就是根，10就是minright，释放minright之前要将parent的右与minright的右链接起来。
迭代
#include<iostream> #include<vector> using namespace std; template<class K> struct BSTNode//树结点 { BSTNode(K key) :_key(key) ,left(nullptr) ,right(nullptr) {} K _key;//结点值 BSTNode<K>* left;//左子树 BSTNode<K>* right;//右子树 }; template<class K> class BSTree//树 { typedef BSTNode<K> Node; public: BSTree() :_root(nullptr) {} bool Insert(const K& key)//插入数据 { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = cur; while (cur)//不等于空就一直找适合插入的位置 { if (cur->_key < key) { parent = cur; cur = cur->right; } else if (cur->_key > key) { parent = cur; cur = cur->left; } else return false; } cur = new Node(key); if (parent->_key > key) parent->left = cur; else parent->right = cur; return true; } bool Find(const K& key)//查找 { Node* cur = _root; if (cur == nullptr) { return false; } while (cur) { if (cur->_key > key) cur = cur->left; else if (cur ->_key < key) cur = cur->right; else { return true; } } return false; } bool Erase(const K& key)//删除数据 { if (_root == nullptr) { return false; } Node* cur = _root; Node* parent = cur; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->right; } else if (cur->_key > key) { parent = cur; cur = cur->left; } else { if (cur->left == nullptr)//只有右孩子 { if (cur == _root) { _root = cur->right; } else if (parent->left == cur) { parent->left = cur->right; } else { parent->right = cur->right; } delete cur;//释放结点 } else if (cur->right == nullptr)//只有左孩子 { if (cur == _root) { _root = cur->left; } else if (parent->left == cur) { parent->left = cur->left; } else { parent->right = cur->left; } delete cur;//释放结点 } else//有两个孩子 { Node* minright = cur->right; parent = cur; while (minright->left)//找到右子树最小值 { parent = minright; minright = minright->left; } //赋值 cur->_key = minright->_key; //链接 if (parent->left == minright) parent->left = minright->right; else parent->right = minright->right; delete minright; } return true; } } return false; } void _InOrder()//因为不想让外界访问道内部的_root，所以只能通过成员函数内部访问 { InOrder(_root); cout << endl; } private: void InOrder(Node* root)//中序遍历 { if (root == nullptr) { return; } InOrder(root->left); cout << root->_key << ' '; InOrder(root->right); } Node* _root;//树的根结点 };
