目录
1.什么是二叉搜索树
2.二叉搜索树的节点构成
搜索二叉树是在二叉树的基础上构成的所以二叉树的节点是
class BSTNode
{
private:
int _data;
BSTNode *left;
BSTNode *right;
};
我们可以在此基础上进行优化。我们可以思考二叉树中的_data一定是为int类型的吗?不一定可能是char可能是其他,所以为了兼容性使得代码的更加全面。我们可以使用模版。
temlate <typname T>
class BSTNode
{
private:
T _data;
BSTNode<T> *left;
BSTNode<T> *right;
};
为了方便维护我们借鉴list的思维,再创造一个类BSTree来存放BSTNode节点。将节点和树分开来。
template <typename T>
class BSTree
{
private:
typedef BSTNode<T> Node;
typedef Node* PNode;
PNode _root;//非内置类型,要写构造函数
};
3.二叉搜索树的 增加,查找,删除
1.查找
查找的目的是为了增加和删除。如果二叉搜索树中有这个要增加的值就不会再往树中增加了,同理如果二叉搜索树中没有这个要删除的树就不需要删除了。
查找的逻辑很简单,因为二叉搜索树的结构决定了它简单的逻辑。“左小右大”。所以我们只需要去拿要找的值key一个一个去比较,如果key比节点的值大就往右找,如果比节点的值小就往左找。
bool Find(const T& data)
{
PNode cur = _root;
while (cur)
{
if (data > cur->_data)
cur = cur->right;
else if (data < cur->_data)
cur = cur->left;
else
return true;
}
return false;
}
2.增加
写了查找函数后方便缕清我们写增加函数的逻辑了。
我们如何增加一个数据到二叉树中呢?首先我们得知道这个数有没有存在于二叉搜索树中吧,如果树中没有这个数据那么我们进行插入操作,接着同样的还需要去遍历一遍树找到要插入的数据的位置,同与节点的值去比较的方式,如果大于节点的值就往右遍历,如果小于节点的值就往左遍历,直到没有值进行比较,此时就代表找到这个值插入的位置了。这里需要注意要插入节点,那就还需要找到插入位置的父节点,通过父节点的指向将新节点插入树中。大致思路是这样的,但还有一些小细节需要我们分类讨论。
1.树为空
2.树不为空,插入节点是父节点的左边还是右边。
代码如下
bool Insert(const T& a)
{
if (Find(a)) //如果树中已经有a值了就不需要插入,直接返回false代表插入失败。
return false;
if (_root == nullptr) //如果树为空,那么直接创个节点将节点地址赋给_root。
{
_root = new Node(a);
return true; //直接返回true代表插入成功。
}
PNode newnode = new Node(a);
PNode cur = _root;
while (cur)
{
if(a > cur->_data)
{
if (cur->right == nullptr)
break;
cur = cur->right;
}
else if(a < cur->_data)
{
if (cur->left == nullptr)
break;
cur = cur->left;
}
}
//遍历结束找到插入位置。
//判断插入的是父节点的左右
if (a > cur->_data) //如果进入了这个if条件代表是父节点的右边。
cur->right = newnode;
else //同理这个就是父节点的左边。
cur->left = newnode;
return true; //最后返回true代表插入成功了。
}
//函数中有两处return true的地方是因为这两种情况不会同时发生,是相互独立的情况,所以每一处都要写上return true。
3.删除
二叉树最麻烦的,最考验代码的逻辑能力的就是删除操作了。因为删除需要考虑多的情况。以下图为例。
看图我们可以发现三组,我们将要删除的节点分组分别是
孩子数为0的节点:0,3,6,11。
孩子数为1的节点:2,7,5。
孩子数为2的节点:1,4,10。
所以我们要分三种情况来讨论。
为了方便叙述我们将要删除节点称为cur,将cur的父节点称为pcur。
1.孩子数为0的情况
类比链表删除的思路,我们只需要找到pcur,将pcur的指向改为空就行。因此我们还需要找到pcur节点。找到pcur节点后我们就需要对其进行讨论pcur为不为空,如果为空意味着cur节点是_root节点,且我们将pcur指向改变时必定会访问pcur所指向的空间,那么此时就会出现空指针的访问问题。
2.孩子数为1的情况
此情况和孩子数为0时的思路大差不差,唯一不同的就是在pcur不为空的情况下,要考虑如何将pcur指向cur的孩子,这是就要判断一:孩子是在cur的左边还是右边,且还要判断二:cur是在pcur的左边还是右边了。判断一和判断二是平行的关系所以谁前谁后并没有影响。
3.孩子数为2的情况
这种情况最麻烦,因为我们要考虑谁来替代cur节点。为了不破坏搜索二叉树的结果特性(左小右大),要来替代的值应该在排完序后cur的左边或者右边。这样才是最优的。我们选择升序的右边,也就是cur右子树的最左节点。我们将cur_right_left_min称为这个右子树的最左节点。
这时我们就要讨论cur_right_left_min存在的问题了。
如果存在和孩子数为1的情况一样在将cur的值替代成cur_right_left_min的值后我们需要将cur_right_left_min的右节点赋给cur_right_left_min的左边即可。
如果不存在也就是cur_right_left_min为空,此时cur的左边右边都可以来替代cur的值,为了代码更强的逻辑性,我们和之前一样选择cur的右子树。此时我们只需将右子树的值赋给cur然后将cur的右边指向空,最后将右子树delete就行了。
最后我们整理思路可以将孩子数为1和孩子数为0的情况放在一起。代码如下:
//用引用是因为,T可能是类,那么加上引用会减少拷贝构造函数的调用。
bool Erase(const T& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_data < key)
{
parent = cur;
cur = cur->right;
}
else if (cur->_data > key)
{
parent = cur;
cur = cur->left;
}
else
{
// 删除
// 0-1个孩子的情况
if (cur->left == nullptr)
{
//考虑parent节点为空节点
if (parent == nullptr)
_root = cur->right;
else
{
if (parent->_data > key)//确定删除的是父节点的左边
parent->left = cur->right;
else
parent->right = cur->right;
}
delete cur;
cur = nullptr;
return true;
}
else if (cur->right == nullptr)
{
if (parent == nullptr)
_root = cur->left;
else
{
if (parent->_data > key)//确定删除的是父节点的左边
parent->left = cur->left;
else
parent->right = cur->left;
}
delete cur;
cur = nullptr;
return true;
}
else
{
// 2个孩子的情况
// 右子树的最小节点作为替代节点
PNode cur_left_min = cur->right;
PNode pcur_left_min = cur;
while (cur_left_min->left)
{
pcur_left_min = cur_left_min;
cur_left_min = cur_left_min->left;
}
if (cur_left_min->left == nullptr)
pcur_left_min->right = cur_left_min->right;
else
pcur_left_min->left = cur_left_min->right;
cur->_data = cur_left_min->_data;
delete cur_left_min;
cur_left_min = nullptr;
return true;
}
}
}
return false;
}