二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
1.原理
二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,O(log(n)).
2.代码实现
整体
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const double EPS = 1E-6;
template<typename T>struct node
{
T value;
node<T>* parent = nullptr;
node<T>* left = nullptr;
node<T>* right = nullptr;
node(const T &v = 0) :value(v) { };
T operator * ()
{
return value;
}
};
template<typename T> class BST
{
private:
node<T>* root = nullptr;
int SIZE = 0;
public:
BST() {};
BST(vector<T> v);
node<T>* GetRoot() { return root; }
bool empty() { return SIZE == 0; }
int size() { return SIZE; }
node<T>* find(const T &v);
node<T>* find_predecessor(const T &v);//寻找前驱节点
node<T>* find_successor(const T &v);//寻找后继节点
node<T>* find_predecessor(node<T>* n);
node<T>* find_successor(node<T>* n);
void insert(const T &v);
void insert(node<T>* n);
void erase(node<T>* n);
bool erase(const T &v);
void clear();
//void traversal(node<T>* root, void(*func)(T v) = [](T v)->void {cout << value << " "; });//遍历输出所有节点
void traversal();
};
template<typename T> BST<T>::BST(vector<T> v) :BST()
{
for (auto n : v)//C++11支持的冒号遍历
insert(n); //auto的作用是自动选择相应的类型
return;
}
template<typename T> node<T>* BST<T>::find(const T &v)
{//二叉搜索树的查找,只需和父节点的值比较即可找到
node<T>* temp = root;
while (temp != nullptr)//temp为空时就表明没找到
{
if (v == temp->value)//找到就返回
return temp;
else
{
if (v < temp->value)
temp = temp->left;
else
temp = temp->right;
}
}
return nullptr;
}
//节点x的前驱,就是指key值小于x.key的节点中key值最大的那个
//若x的左子树不为空,则x前驱是x节点左子树里最靠右的那个节点
//如果x的左子树为空,那么我们就要向上找x的第一个有右孩子且左子树里没有x节点的祖先。
template<typename T> node<T>* BST<T>::find_predecessor(const T &v)
{
node<T>* n = find(v);
return n == nullptr ? nullptr : find_predecessor(n);
}
template<typename T> node<T>* BST<T>::find_predecessor(node<T>* n)
{
node<T>* temp = n;
if (temp->left != nullptr)//如果节点有左子树
{
temp = temp->left;
while (temp->right != nullptr)//找左子树中最右边的叶子
temp = temp->right;
return temp;
}
while (temp->parent != nullptr && temp->parent->left == temp)
temp = temp->parent;
return temp->parent;
}
//节点x的后继,就是指key值大于x.key的节点中key值最小的那个
//若x的右子树不为空,则x后继是x节点右子树里最靠左的那个节点
//如果x的右子树为空,那么我们就要向上找x的第一个有左孩子且右子树里没有x节点的祖先。
template<typename T> node<T>* BST<T>::find_successor(const T &v)
{
node<T>* n = find(v);
return n == nullptr ? nullptr : find_successor(n);
}
template<typename T> node <T>* BST<T>::find_successor(node<T>* n)
{
node<T>* temp = n;
if (temp->right != nullptr)//若右子树不为空
{
temp = temp->right;
while (temp->left != nullptr)//找右子树中最左边的叶子
temp = temp->left;
return temp;
}
while (temp->parent != nullptr && temp->parent->right != temp)
temp = temp->parent;
return temp->parent;
}
//新插入的节点一定会取代一个原来的叶子节点,我们只要确定被取代的是哪一个叶子节点就行了
//我们从根节点开始,利用二叉搜索树的性质比对值来向下查找,直到到达最后的叶子节点,这个节点就是要用插入节点替换的叶子节点。
template<typename T> void BST<T>::insert(const T &v)
{
node<T>* n = new node<T>(v);
insert(n);
return;
}
template<typename T> void BST<T>::insert(node<T>* n)
{
node<T>* temp = root;
SIZE++;
if (temp == nullptr)
{//如果根节点为空,则直接插入
root = n;
return;
}
while (true)//循环找出插入的位置
{
if (temp->value > n->value)
{//插入在左子树的情况
if (temp->left != nullptr)
temp = temp->left;//左子树不为空则继续找
else
{
temp->left = n;//如果左子树为空则直接插入
n->parent = temp;//修改父节点为temp指向的节点
return;
}
}
else
{//插入右子树的情况,同上
if (temp->right != nullptr)
temp = temp->right;
else
{
temp->right = n;
n->parent = temp;
return;
}
}
}
return;
}
//删除的情况比插入复杂,一共有3种可能的情况。
//1,被删除的节点x没有NIL节点以外的孩子节点时,直接删除,修改父节点指针指向NIL节点即可。
//2,被删除的节点x只有一个孩子时,用这个孩子节点替换被删除节点的位置即可。
//3,被删除的节点x有两个孩子时,我们就要查找x节点的后继y节点,注意y节点一定在x节点的右子树中而且y节点没有左孩子,此时,我们先用y节点的右孩子代替y节点原先的位置,然后再用y节点代替x节点位置即可完成删除操作。
template<typename T> bool BST<T>::erase(const T &v)
{
node<T>* temp = find(v);
if (temp != nullptr)
erase(temp);
else
return false;
return true;
}
template<typename T> void BST<T>::erase(node<T>* n)
{
SIZE--;
node<T>* temp;
if (n->left == nullptr && n->right == nullptr)
temp = nullptr;//情况1:没有子节点
else if (n->left == nullptr || n->right == nullptr)
{//情况2:有一个子节点
temp = n->left == nullptr ? n->right : n->left;
temp->parent = n->parent;//因为temp要取代n,所以temp要完全复制n的信息。又因temp是n的一个子节点,故只需复制n的parent就够了
}
else//情况3:有两个子节点
{
temp = find_successor(n);//用n节点的后继y来取代n
node<T>* successor_right;//后继y可能有右儿子,所以需要先用y的右儿子取代y,再让y取代n
if (temp->right == nullptr)//没有右儿子的话就用nullptr来取代y
successor_right = nullptr;
else
{
successor_right = temp->right;
successor_right->parent = temp->parent;//用y的右儿子取代y
}
if (temp->parent->left == temp)//这里用来修改y的父节点,使y的右儿子完全取代y
temp->parent->left = successor_right;
else
temp->parent->right = successor_right;
//至此,对y的处理就已经完成了。接下来就是让y取代n了
//这一步只需要把y的值赋值给n,然后删除y就好了
n->value = temp->value;
delete temp;
return;
}
//情况一和情况二到此为止取代n节点的temp已经确定,而且当temp不是nullptr的时候,temp也已经复制了必要的n的属性,剩下的就是让n的父节点指向temp了
//注意被删除的节点有可能是根节点,所以当我们发现被删除的是根节点时,不需要让n的父节点指向temp,因为n没有父节点了,但是这个时候必须修改root指针的指向
if (n->parent != nullptr)
{
if (n->parent->left == temp)
n->parent->left = temp;
else
n->parent->right = temp;
}
else
root = temp;
delete n;
return;
}
template<typename T>void BST<T>::clear()
{
if (root == nullptr)
return;
queue<node<T>*> q;
q.push(root);
while (!q.empty())
{
node<T>* temp = q.front();
q.pop();
if (temp->left != nullptr)
q.push(temp->left);
if (temp->right != nullptr)
q.push(temp->right);
delete temp;
SIZE--;
}
root = nullptr;
return;
}
//第一个参数是为了进行递归而设立的。
//第二个参数是一个函数指针,这个函数指针指向一个没有返回值同时有一个int类型参数的函数,
//并且我用lambda表达式给这个函数指针赋了一个默认值,这个默认函数的功能是输出参数k,用来遍历输出每一个节点的值,
//大家可以用别的lambda表达式或者函数来覆盖这个默认值,以达到定制功能的目的
//template<typename T> void BST<T>::traversal(node<T>* root, void(*func)(T v))
//{
// if (root = nullptr)
// return;
//
// traversal(root->left);
// func(root->value);
// traversal(root->right);
//
// return;
//}
template<typename T> void BST<T>::traversal()
{//广搜遍历输出
if (root == nullptr)
return;
queue<node<T>*> q;
q.push(root);
while (!q.empty())
{
node<T>* temp = q.front();
q.pop();
cout << temp->value << " ";
if (temp->left != nullptr)
q.push(temp->left);
if (temp->right != nullptr)
q.push(temp->right);
}
return;
}
输出的那一块注释掉的是lambda语法写的输出。因为我这里写的是模板类,导致会有错误。把所有和模板有关的改成int就可以用了。
前中后序遍历后面再写吧。