特性：
- a. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值
- b. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
- c. 它的左、右子树也分别为排序二叉树
优点：
因为左子节点总是比父节点小，右子节点总是比父节点大，因此可以使用二分查找提高速度。
算法：
- 查找，插入，删除，遍历
查找： 已知，查找一个节点key
- a. 若key小于当前节点，则跟当前节点左子节点比较
- b. 若key大于当前节点，则跟当前节点右子节点比较
- c. 若key等于当前节点，则返回当前节点引用
- d. 若没有找到节点，则返回已查找到最后一个节点的左/右子节点引用（此返回的引用值为nullptr）
- e. 重复a, b
插入： 已知，插入一个节点key
- a.查询key
- c.若返回无效引用，则key替换引用
- c.若返回有效引用，则忽略本次操作
删除： 已知，删除一个节点key
- a.查询key
- b.若返回无效引用，则忽略本次操作
- c.若返回有效引用，则操作如下：
- --- a.若引用左/右子节点同时不为空，则以中序优先查询到key的直接前驱，将前驱替换到key的位置，最后删除key
- --- b.若引用左子节点不为空，则删除引用左子节点
- --- c.若引用右自己点不为空，则删除引用右子节点
- --- d.若引用为叶子节点，则直接删除引用
遍历： 二叉树遍历算法即可
配图： 略
C++实现：
#include <string>
#include <iostream>
#include <functional>
#define SAFE_DELETE(p) delete p; p = nullptr;
template <class Key, class Value>
struct STNode {
STNode(const Key & k, const Value & v)
: parent(nullptr), rchild(nullptr)
, lchild(nullptr), key(k), val(v)
{ }
~STNode()
{
SAFE_DELETE(lchild);
SAFE_DELETE(rchild);
}
Key key;
Value val;
STNode *parent, *rchild, *lchild;
};
template <class Key, class Value>
class STree {
public:
typedef STNode<Key, Value> Node;
public:
STree() : _root(nullptr)
{ }
~STree()
{
SAFE_DELETE(_root);
}
void ForEach(const std::function<void (Node *)> & fn)
{
ForEach(_root, fn);
}
Node * Query(const Key & key)
{
return Query(_root, key);
}
size_t GetSize()
{
return GetSize(_root);
}
bool IsEmpty()
{
return nullptr != _root;
}
bool Insert(const Key & key, const Value & val)
{
auto parent = (Node *)nullptr;
auto &insert = Query(_root, key, &parent);
if (nullptr == insert)
{
insert = new Node(key, val);
insert->parent = parent;
return true;
}
return false;
}
void Remove(const Key & key)
{
if (auto &del = Query(_root, key)) { Remove(del); }
}
private:
size_t GetSize(Node * node)
{
if (nullptr != node)
{
auto ln = GetSize(node->lchild);
auto rn = GetSize(node->rchild);
return 1 + ln + rn;
}
return 0;
}
void Remove(Node *& node)
{
// 三种情况:
// 1，叶子节点,
// 2，一个子节点,
// 3，两个子节点
auto del = node;
if (nullptr != node->lchild && nullptr != node->rchild)
{
// 中序遍历，找到直接前驱
auto pre = node->lchild;
while (nullptr != pre->rchild)
{
pre = pre->rchild;
}
if (node->lchild == pre)
{
pre->parent = node->parent;
pre->rchild = node->rchild;
}
else
{
if (nullptr != pre->lchild)
{
pre->lchild->parent = pre->parent;
}
pre->parent->rchild = pre->lchild;
pre->lchild = node->lchild;
pre->rchild = node->rchild;
pre->parent = node->parent;
node->lchild->parent = pre;
node->rchild->parent = pre;
}
node = pre;
}
else if (nullptr != node->lchild)
{
node->lchild->parent = node->parent;
node = node->lchild;
}
else if (nullptr != node->rchild)
{
node->rchild->parent = node->parent;
node = node->rchild;
}
else
{
node = nullptr;
}
del->lchild = nullptr;
del->rchild = nullptr;
SAFE_DELETE(del);
}
Node *& Query(Node *& node, const Key & key, Node ** parent = nullptr)
{
if (nullptr != node && node->key != key)
{
if (nullptr != parent)
*parent = node;
return Query(node->key > key
? node->lchild
: node->rchild, key, parent);
}
return node;
}
void ForEach(Node * node, const std::function<void(Node *)> & fn)
{
if (nullptr != node)
{
ForEach(node->lchild, fn);
ForEach(node->rchild, fn);
fn(node);
}
}
private:
Node *_root;
};
int main()
{
STree<int, std::string> tree;
tree.Insert(50, "val 50");
tree.Insert(60, "val 50");
tree.Insert(40, "val 40");
tree.Insert(70, "val 70");
tree.Insert(30, "val 30");
std::cout << tree.GetSize() << std::endl;
tree.ForEach([&](STNode<int, std::string> * node) {
std::cout << node->key << ": " << node->val << std::endl;
tree.Remove(node->key);
});
std::cout << tree.GetSize() << std::endl;
return 0;
}
结束语：
本博文只讲述二叉排序树的原理以及C++简单实现
网友评论