特性：

• a. 若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值
• b. 若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值
• c. 它的左、右子樹也分別為排序二叉樹

優(yōu)點(diǎn)：
因?yàn)樽笞庸?jié)點(diǎn)總是比父節(jié)點(diǎn)小，右子節(jié)點(diǎn)總是比父節(jié)點(diǎn)大，因此可以使用二分查找提高速度。

算法：

• 查找，插入，刪除，遍歷

查找： 已知，查找一個(gè)節(jié)點(diǎn)key

• a. 若key小于當(dāng)前節(jié)點(diǎn)，則跟當(dāng)前節(jié)點(diǎn)左子節(jié)點(diǎn)比較
• b. 若key大于當(dāng)前節(jié)點(diǎn)，則跟當(dāng)前節(jié)點(diǎn)右子節(jié)點(diǎn)比較
• c. 若key等于當(dāng)前節(jié)點(diǎn)，則返回當(dāng)前節(jié)點(diǎn)引用
• d. 若沒有找到節(jié)點(diǎn)，則返回已查找到最后一個(gè)節(jié)點(diǎn)的左/右子節(jié)點(diǎn)引用（此返回的引用值為nullptr）
• e. 重復(fù)a, b

插入： 已知，插入一個(gè)節(jié)點(diǎn)key

• a.查詢key
• c.若返回?zé)o效引用，則key替換引用
• c.若返回有效引用，則忽略本次操作

刪除： 已知，刪除一個(gè)節(jié)點(diǎn)key

• a.查詢key
• b.若返回?zé)o效引用，則忽略本次操作
• c.若返回有效引用，則操作如下：
• --- a.若引用左/右子節(jié)點(diǎn)同時(shí)不為空，則以中序優(yōu)先查詢到key的直接前驅(qū)，將前驅(qū)替換到key的位置，最后刪除key
• --- b.若引用左子節(jié)點(diǎn)不為空，則刪除引用左子節(jié)點(diǎn)
• --- c.若引用右自己點(diǎn)不為空，則刪除引用右子節(jié)點(diǎn)
• --- d.若引用為葉子節(jié)點(diǎn)，則直接刪除引用

遍歷： 二叉樹遍歷算法即可

配圖： 略

C++實(shí)現(xiàn)：

#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，葉子節(jié)點(diǎn), 
        //  2，一個(gè)子節(jié)點(diǎn), 
        //  3，兩個(gè)子節(jié)點(diǎn)
        auto del = node;
        if (nullptr != node->lchild && nullptr != node->rchild)
        {
            //  中序遍歷，找到直接前驅(qū)
            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;
}

結(jié)束語(yǔ)：

本博文只講述二叉排序樹的原理以及C++簡(jiǎn)單實(shí)現(xiàn)