bosthhe1
commented
1 year ago template<class T>
class BSTree
{
typedef BSNode<T> BSNode;
public:
BSTree(const T a = T())
:node(new BSNode(a))
{}
bool insertNode(const T key)
{
BSNode* parent = node;
BSNode* cur = node;
while (cur)
{
if (cur->a < key)
{
parent = cur;
cur = cur->right;
}
else if (cur->a > key)
{
parent = cur;
cur = cur->left;
}
else
return false;
if (cur == nullptr)
{
BSNode* newnode =new BSNode(key);
if (parent->a > key)
{
parent->left = newnode;
}
else
{
parent->right = newnode;
}
}
}
}
bool Erase(const T& key)
{
return _Erase(node,key);
}
bool RErase(const T& key)
{
return _RErase(node, key);
}
BSNode* find(const T& key)
{
return _find(node, key);
}
void inorder()
{
_inorder(node);
}
BSNode* Rfind(const T& key)
{
return _Rfind(node,key);
}
bool RinsertNode(const T key)
{
return _RinsertNode(node, key);
}
private:
bool _RinsertNode(BSNode*& root, const T& key)
{
if (root == nullptr)
{
root = new BSNode(key);
return true;
}
if (root->a > key)
{
return _RinsertNode(root->left, key);
}
else if (root->a < key)
{
return _RinsertNode(root->right, key);
}
else
return false;
}
BSNode* _Rfind(BSNode* root,const T& key)
{
if (root == nullptr)
{
return nullptr;
}
if (root->a > key)
{
return _Rfind(root->left, key);
}
else if (root->a < key)
{
return _Rfind(root->right, key);
}
else
return root;
}
bool _RErase(BSNode*& root, const T& key)
{
if (root == nullptr)
return false;
if (root->a > key)
{
return _RErase(root->left, key);
}
else if (root->a < key)
{
return _RErase(root->right, key);
}
else
{
if (root->left == nullptr)
{
root = root->right;
}
else if (root->right==nullptr)
{
root = root->left;
}
else
{
BSNode* min = root->left;
while (min->right)
{
min = min->right;
}
std::swap(root->a, min->a);
_RErase(root->left, key);
return true;
}
}
}
bool _Erase(BSNode* root, const T& key)
{
BSNode* cur = root;
BSNode* parent = root;
while (cur)
{
if (cur->a > key)
{
parent = cur;
cur = cur->left;
}
else if (cur->a < key)
{
parent = cur;
cur = cur->right;
}
else//cur->a ==key
{
BSNode* del = cur;
//左为空，或者又为空
if (cur->left == nullptr || cur->right == nullptr)
{
if (parent->left == cur)
{
if (cur->left == nullptr)
{
parent->left = cur->right;
}
else if (cur->right == nullptr)
{
parent->left = cur->left;
}
}
else
{
if (cur->left == nullptr)
{
parent->right = cur->right;
}
else if (cur->right == nullptr)
{
parent->right = cur->left;
}
}
delete cur;
return true;
}
//都不为空，使用的是交换法，将左子树的最大值，或者右子树的最小值进行交换，然后将key值删除，因为交换后key的左孩子或者有孩子一定为空，因为遍历的就是最左或最右(所以不存在节点有两个孩子都不为空的情况。)，所以再用前面的方法删除节点
else
{
BSNode* min = cur->left;
BSNode* minparent = cur;
while (min->right)//找左最大替换 ，min节点可能存在右孩子，如果有右孩子会递归下去
{
minparent = min;
min = min->right;
}
cur->a = min->a;
if (minparent->left == min)//这里是确认孩子是左孩子还是右孩子
{
minparent->left = min->left; //min的右边为空，只能直向左边
}
else
{
minparent->right = min->left;//min的右边为空，只能直向左边
}
delete min;
return true;
}
}
}
return false;
}
BSNode* _find(BSNode* root, const T& key)
{
BSNode* cur = root;
while (cur)
{
if (cur->a>key)
{
cur = cur->left;
}
else if (cur->a < key)
{
cur = cur->right;
}
else if (cur == nullptr)
return nullptr;
else
return cur;
}
}
void _inorder(BSNode* root)
{
if (root == nullptr)
return;
_inorder(root->left);
std::cout << root->a << " ";
_inorder(root->right);
}
private:
BSNode* node;
};
搜索二叉树是一种特殊的二叉树结构，二叉树的左孩子的值，永远比根节点值小，二叉树的右孩子的值，永远比根节点值大，所以搜索二叉树只需要将值进行比较，就能很快锁定值的位置，最好时间复杂度为高度次(log2N), 最坏的时间复杂度为O(N)单链表的形式，搜索二叉树的功能是排序+去重，只要构建出来，每一个节点就都会存在固定的位置。 由于搜索二叉树的特别性质，所以搜索二叉树的走中序，是一个从小到大的递增。 搜索二叉树的构建中，插入是很简单的，只要注意下需要带父节点，或者带二级指针改变节点的链接即可，但是删除很麻烦，删除的话需要分情况，如果删除的节点没有孩子或者只有一个孩子，就可以直接托孤，将节点的孩子给父亲，但是需要注意的节点时父节点的哪一个孩子，如果删除节点是有两个孩子，就需用到替换的方法，将值替换掉，这个值必须满足比左边所有节点都打，比右边所有节点都小，所有就会存在两个值，这种情况随便选一个交换即可，交换后，问题变为删除被替换的节点，哪个节点一定是一个极端，要么没有孩子，要么只有一个左孩子或者右孩子，这时候再来处理就方便很多