今天重写了一遍二叉搜索树,在这里记录一下吧。
1.二分查找法定义
二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
2.二叉查找树(Binary Search Tree)基础
二叉查找树也可叫做二分查找树。
它不仅可以查找数据,还可以高效地插入、删除数据。
特点:每个节点的key值大于左子节点,小于右子节点。
注意它不一定是完全的二叉树。
二叉查找树有两个属性:
- 所有节点都比左子树中的节点大
- 所有节点都小于右子树中的节点
通过这两个属性,可以推断出以下结论:
- 二叉查找树最小的节点位于最顶端节点的最左边子树行的末尾(如图数字 3 )
- 二叉查找树的最大节点位于最顶端节点的最右边的子树行的末尾(如图数字 28 )
3.代码实现
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Node
{
int value;
Node* parent = nullptr;
Node* left = nullptr;
Node* right = nullptr;
Node(const int &v = 0) :value(v) { };
int operator * ()
{
return value;
}
};
class BST
{
private:
Node* root = nullptr;
int SIZE = 0;
/*查找节点前驱,后继*/
Node* find_predecessor(Node* n);
Node* find_successor(Node* n);
/*插入,删除*/
bool insert(Node* n);
bool erase(Node* n);
/*三序遍历*/
void __preorderTraversal(Node* node, vector<int> &res);
void __inorderTraversal(Node* node, vector<int> &res);
void __postorderTraversal(Node* node, vector<int> &res);
public:
/*构造,析构*/
BST() :root(nullptr), SIZE(0) { }
BST(vector<int> data);
~BST();
/*二叉搜索树的信息*/
Node* begin() { return root; }
bool empty() { return SIZE == 0; }
int size() { return SIZE; }
/*查找*/
Node* find(const int &data);
Node* find_predecessor(const int &v);//寻找前驱节点
Node* find_successor(const int &v);//寻找后继节点
/*插入,删除*/
bool insert(const int &v);
bool erase(const int &v);
void clear();
/*三序遍历*/
vector<int> preorderTraversal(Node* node);
vector<int> inorderTraversal(Node* node);
vector<int> postorderTraversal(Node* node);
/*其他*/
void traversal(Node* node, void(*func)(int data) = [](int data)->void {cout << data << " "; });//遍历输出所有节点
};
BST::BST(vector<int> data)
{
for (auto n : data)//C++11支持的冒号遍历
insert(n); //auto的作用是自动选择相应的类型
return;
}
BST::~BST()
{
clear();
return;
}
/*****************************************************************
Function:find_predecessor
Description:查找节点的前驱。
节点x的前驱,就是指value小于x节点中value最大的那个节点
若x的左子树不为空,则x前驱是x节点左子树里最靠右的那个节点
如果x的左子树为空,那么我们就要向上找x的第一个有右孩子且左子树里没有
x节点的祖先。
*****************************************************************/
Node * BST::find_predecessor(const int & data)
{
Node* tmp = find(data);
return tmp == nullptr ? nullptr : find_predecessor(tmp);
}
Node * BST::find_predecessor(Node * n)
{
Node* tmp = n;
if (tmp->left != nullptr)
{//当左子树不为空的时候
tmp = tmp->left;
while (tmp->right != nullptr)
tmp = tmp->right;//寻找左子树中最右边的节点
return tmp;
}
while (tmp->parent != nullptr && tmp->parent->left == tmp)
tmp = tmp->parent;//找x的第一个有右孩子且左子树里没有x节点的祖先
return tmp->parent;
}
/*****************************************************************
Function:find_predecessor
Description:查找节点的后继。
节点x的后继,就是指value大于x节点中value最小的那个节点
若x的右子树不为空,则x后继是x节点右子树里最靠左的那个节点
如果x的右子树为空,那么我们就要向上找x的第一个有左孩子且右子树里
没有x节点的祖先。
*****************************************************************/
Node * BST::find_successor(const int & data)
{
Node* tmp = find(data);
return tmp == nullptr ? nullptr : find_successor(data);
}
Node * BST::find_successor(Node * n)
{
Node* tmp = n;
if (tmp->right != nullptr)
{
tmp = tmp->right;
while (tmp->left != nullptr)
tmp = tmp->left;
return tmp;
}
while (tmp->parent != nullptr && tmp->parent->right != tmp)
tmp = tmp->parent;//向上找x的第一个有左孩子且右子树里没有x节点的祖先
return tmp->parent;
}
/*****************************************************************
Function:find
Description:查找值为data的节点。
*****************************************************************/
Node * BST::find(const int & data)
{
Node* tmp = root;
while (tmp != nullptr && tmp->value != data)
tmp = data > tmp->value ? tmp->right : tmp->left;
return tmp;
}
/*****************************************************************
Function:insert
Description:向树中插入值data。
新插入的节点一定会取代一个原来的叶子节点,我们只要确定被取代的是
哪一个叶子节点就行了。
我们从根节点开始,利用二叉搜索树的性质比对值来向下查找,直到到达
最后的叶子节点,这个节点就是要用插入节点替换的叶子节点。
*****************************************************************/
bool BST::insert(const int & data)
{
Node* tmp = new Node();
return insert(tmp);
}
bool BST::insert(Node * n)
{
Node* tmp = n;
SIZE++;
if (root == nullptr)
{
root = n;//如果根节点为空则直接插入
return true;
}
while (true)//循环找出插入点
{
if (tmp->value > n->value)
{//插入在左子树的情况
if (tmp->left != nullptr)
tmp = tmp->left;//左子树不为空则继续找
else
{
tmp->left = n;//如果左子树为空则直接插入
n->parent = tmp;//修改父节点为tmp指向的节点
return true;
}
}
else
{//插入右子树的情况,同上
if (tmp->right != nullptr)
tmp = tmp->right;
else
{
tmp->right = n;
n->parent = tmp;
return true;
}
}
}
return false;
}
/*****************************************************************
Function:erase
Description:从二叉树中删除node节点,返回删除是否成功。
删除的情况比插入复杂,一共有3种可能的情况。
1. 被删除的节点x没有nullptr节点以外的孩子节点时,直接删除,修改
父节点指针指向nullptr节点即可。
2. 被删除的节点x只有一个孩子时,用这个孩子节点替换被删除节点的位
置即可。
3. 被删除的节点x有两个孩子时,我们就要查找x节点的后继y节点,注意
y节点一定在x节点的右子树中而且y节点没有左孩子,此时,我们先用y节
点的右孩子代替y节点原先的位置,然后再用y节点代替x节点位置即可完
成删除操作。
*****************************************************************/
bool BST::erase(Node * n)
{
if (n == nullptr)
return false;
SIZE--;
Node* tmp = n;
if (n->left == nullptr && n->right == nullptr)//没有子节点
tmp = nullptr;
else if (n->left == nullptr || n->right == nullptr)
{//一个子节点
tmp = n->left == nullptr ? n->right : n->left;
tmp->parent = n->parent;
/*因为tmp要取代n,所以tmp要完全复制n的信息。
又因tmp是n的一个子节点,故只需复制n的parent就够了*/
}
else//有两个子节点
{
tmp = find_successor(n);//用n节点的后继y来取代n
Node* successor_right;
//后继y可能有右儿子,所以需要先用y的右儿子取代y,再让y取代n
if (tmp->right == nullptr)//没有右儿子的话就用nullptr来取代y
successor_right = nullptr;
else
{
successor_right = tmp->right;
successor_right->parent = tmp->parent;//用y的右儿子取代y
}
/* 这里用来修改y的父节点,使y的右儿子完全取代y */
if (tmp->parent->left == tmp)
tmp->parent->left = successor_right;
else
tmp->parent->right = successor_right;
/* 至此,对y的处理就已经完成了。接下来就是让y取代n了
这一步只需要把y的值赋值给n,然后删除y就好了 */
n->value = tmp->value;
delete tmp;
return true;
}
/* 情况一和情况二到此为止取代n节点的tmp已经确定,而且当tmp不是
nullptr的时候,tmp也已经复制了必要的n的属性,剩下的就是让n的
父节点指向tmp了
注意被删除的节点有可能是根节点,所以当我们发现被删除的是根节点
时,不需要让n的父节点指向tmp,因为n没有父节点了,但是这个时候
必须修改root指针的指向 */
if (n->parent != nullptr)
{
if (n->parent->left == tmp)
n->parent->left = tmp;
else
n->parent->right = tmp;
}
else
root = tmp;
delete n;
return true;
}
bool BST::erase(const int & data)
{
return erase(find(data));
}
/*****************************************************************
Function:clear
Description:清空树。
*****************************************************************/
void BST::clear()
{//这里我用了广搜的思想,也可以使用递归
if (root == nullptr)
return;
queue<Node*> q;
q.push(root);
while (!q.empty())
{
Node* tmp = q.front();
q.pop();
if (tmp->left != nullptr)
q.push(tmp->left);
if (tmp->right != nullptr)
q.push(tmp->right);
delete tmp;
SIZE--;
}
root = nullptr;
return;
}
/*****************************************************************
Function:traversal
Description:遍历输出二叉搜索树。
这里解释一下这个lambda语法:
第一个参数是为了进行递归而设立的。
第二个参数是一个函数指针,这个函数指针指向一个没有返回值同时有一个int类型参数
的函数,
并且我用lambda表达式给这个函数指针赋了一个默认值,这个默认函数的功能是输出参
数k,用来遍历输出每一个节点的值,
大家可以用别的lambda表达式或者函数来覆盖这个默认值,以达到定制功能的目的
*****************************************************************/
void BST::traversal(Node* node, void(*func)(int data))
{
if (node = nullptr)
return;
traversal(node->left);
func(node->value);
traversal(node->right);
return;
}
/*****************************************************************
Function:preorderTraversal
Description:前序遍历。
*****************************************************************/
void BST::__preorderTraversal(Node* node, vector<int> &res)
{
if (node)
{
res.push_back(node->value);
__preorderTraversal(node->left, res);
__preorderTraversal(node->right, res);
}
return;
}
vector<int> BST::preorderTraversal(Node* node)
{
vector<int> res;
__preorderTraversal(node, res);
return res;
}
/*****************************************************************
Function:inorderTraversal
Description:中序遍历。
*****************************************************************/
void BST::__inorderTraversal(Node* node, vector<int> &res)
{
if (node)
{
__inorderTraversal(node->left, res);
res.push_back(node->value);
__inorderTraversal(node->right, res);
}
return;
}
vector<int> BST::inorderTraversal(Node* node)
{
vector<int> res;
__inorderTraversal(node, res);
return res;
}
/*****************************************************************
Function:postorderTraversal
Description:后序遍历。
*****************************************************************/
void BST::__postorderTraversal(Node* node, vector<int> &res)
{
if (node)
{
__postorderTraversal(node->left, res);
__postorderTraversal(node->right, res);
res.push_back(node->value);
}
return;
}
vector<int> BST::postorderTraversal(Node* node)
{
vector<int> res;
__postorderTraversal(node, res);
return res;
}