二叉搜索树是一种特殊的二叉树，他的每一个结点都有一个键值，且左结点的值都小于父结点的值，右结点的值都大于父结点的值，这些键值都不能重复。
时间复杂度
一般情况下，插入、查找、删除的时间复杂度为O(logN)。
最坏情况下二叉查找树退化成一个链表，插入、查找、删除的时间复杂度为O(N)。
遍历的时间复杂度为O(N)。
结点的后继：
二叉搜索树的中序遍历是从小到大排序的结果，中序遍历中在某结点后面的结点就是它的后继。
查找结点的后继
- 当结点存在右子树时，由于右子树的值都比它大，所以它的后继就是右子树中最小值得结点，而且它一定是叶子结点。
- 当结点不存在右子树时，只需要不断向它的父结点查找，找到一个比它大的就是它的后继节点。
删除结点
根据要删除结点的子结点的个数分为以下几种情况。
- 当结点不存在子树时，直接将该结点删除。
- 当结点存在右子树或者左子树时，将子树连接到结点的父结点即可。
- 当结点同时存在左右子树时，需要找到该结点的后继替换该结点，再删掉后继节点，因为这样做才可以满足二叉搜索树的性质。
#include <iostream>
#include <queue>
using namespace std;
template<class E>
class TreeNode
{
public:
E key;
TreeNode<E> *parent = nullptr;
TreeNode<E> *left = nullptr;
TreeNode<E> *right = nullptr;
TreeNode(E e)
{
this->key = e;
}
};
template<class E>
class BSTree
{
TreeNode<E> *root;
public:
bool insert(E key);
TreeNode<E> * search(E key);
bool remove(E key);
void levelPrint();
void inOrderPrint();
private:
TreeNode<E> *getSuccessor(TreeNode<E> *node);
TreeNode<E> *getMinimum(TreeNode<E> *node);
bool removeNode(TreeNode<E> *pNode);
void inOrder(TreeNode<E> *node);
};
/**
* 插入结点
* @tparam E
* @param key
* @return
*/
template<class E>
bool BSTree<E>::insert(E key)
{
TreeNode<E> *node = new TreeNode<E>(key);
if (root == nullptr)
root = node;
else
{
TreeNode<E> *current = root;
TreeNode<E> *parent = nullptr;
//循环找到要添加的位置
while(current)
{
parent = current;
if (key < current->key) current = current->left;
else if (key > current->key) current = current->right;
else return false; //二叉搜索树不允许重复，重复添加失败
}
//parent为要添加结点的位置，比较要添加key的大小
if (key < parent->key) parent->left = node;
else parent->right = node;
node->parent = parent;
}
return true;
}
/**
* 查找结点
* @tparam E
* @param key
* @return
*/
template<class E>
TreeNode<E> * BSTree<E>::search(E key)
{
if (root == nullptr) return nullptr;
else
{
TreeNode<E> *current = root;
while (current)
{
if (key < current->key) current = current->left;
else if(key > current->key) current = current->right;
else return current;
}
}
return nullptr;
}
/**
* 层序遍历
* @tparam E
*/
template<class E>
void BSTree<E>::levelPrint()
{
if (root == nullptr) return;
TreeNode<E> *current = root;
queue<TreeNode<E> *> queue;
queue.push(root);
while(!queue.empty())
{
TreeNode<E> * t = queue.front();
queue.pop();
cout<<t->key<<endl;
if (t->left) queue.push(t->left);
if (t->right) queue.push(t->right);
}
}
/**
* 删除指定结点
* 1.指定结点左右都为空时，直接将其删除
* 2.指定结点左或者右为空时，将该子结点连到指定结点的父节点
* 3.指定结点左右都不为空时，找到其右子树中最小结点代替该结点
* @tparam E
* @param key
* @return
*/
template<class E>
bool BSTree<E>::remove(E key)
{
//查找要删除的结点
TreeNode<E> *target = search(key);
return removeNode(target);
}
template<class E>
bool BSTree<E>::removeNode(TreeNode<E> *target)
{
if (target)//这是要删除的结点
{
TreeNode<E> *parent = target->parent;
//子结点都为空
if (target->left == nullptr && target->right == nullptr)
{
if (parent->left == target)
parent->left = nullptr;
else
parent->right = nullptr;
delete target;
}
//左为空
else if (target->left == nullptr)
{
if(parent->left == target)
parent->left = target->right;
else
parent->right = target->right;
delete target;
}
//右为空
else if (target->right == nullptr)
{
if(parent->left == target)
parent->left = target->left;
else
parent->right = target->left;
delete target;
}
//都不为空
else
{
//要删除结点的后继结点
TreeNode<E> *successor = getSuccessor(target);
target->key = successor->key;
removeNode(successor);
}
return true;
}
return false;
}
/**
* 查找node结点的后继结点
* 后继结点：在树中比该结点大的结点，即中序遍历排在其后面的结点
* 1.当node的右结点存在时，其后继是 右子树中最小的结点
* 2.当node的右结点不存在时，往父结点查找他的后继
* @tparam E
* @param node
* @return
*/
template<class E>
TreeNode<E> *BSTree<E>::getSuccessor(TreeNode<E> *node)
{
TreeNode<E> *pNode = node;
if (pNode->right)
return getMinimum(pNode->right);
else
{
TreeNode<E> *parent = node->parent;
//当没有右结点时，找后继有两种方法
//1.直接往父结点找一个比他大的结点就是他的后继
while(parent->key < node->key)
{
parent = parent->parent;
}
//2.往父结点找，并同时移动node和parent，直到node是parent的左结点，parent就是他的后继
// TreeNode<E> *parent = node->parent;
// while(parent && parent->left != node)
// {
// node = parent;
// parent = parent->parent;
// }
return parent;
}
}
/**
* 查找node这颗树种最小的结点
* @tparam E
* @param node
* @return
*/
template<class E>
TreeNode<E> *BSTree<E>::getMinimum(TreeNode<E> *node)
{
//一直往左找
TreeNode<E> *pNode = node;
while (pNode->left)
{
pNode = pNode->left;
}
return pNode;
}
template<class E>
void BSTree<E>::inOrder(TreeNode<E> *node)
{
if (node == nullptr)
return;
inOrder(node->left);
cout<<node->key<<endl;
inOrder(node->right);
}
/**
* 中序遍历
* @tparam E
*/
template<class E>
void BSTree<E>::inOrderPrint()
{
inOrder(root);
}
int main()
{
BSTree<int> *bst = new BSTree<int>();
bst->insert(50);
bst->insert(40);
bst->insert(45);
bst->insert(60);
bst->insert(57);
bst->insert(70);
bst->inOrderPrint();
// TreeNode<int> * t1 = bst->search(65);
// if (t1) cout<<"找到了,key = "<<t1->key<<endl;
//
// TreeNode<int> * t2 = bst->search(62);
// if (t2) cout<<"找到了,key = "<<t2->key<<endl;
// else cout<<"没找到"<<endl;
cout<<"删除测试"<<endl;
bst->remove(45);
bst->inOrderPrint();
return 0;
}
