2.4-数据结构：二叉搜索树

2.4-数据结构-二叉搜索树

本文利用C++实现了数据结构中二叉搜索树的常见接口。

#pragma once
#include <iostream>
using namespace std;

template<class K>
struct BSTreeNode {
    BSTreeNode<K>* _left = nullptr;
    BSTreeNode<K>* _right = nullptr;
    K _key;
    BSTreeNode(K key) : _key(key) {}
};

template<class K>
class BSTree {
    typedef BSTreeNode<K> Node;
public:
    // 构造函数
    BSTree() : _root(nullptr) {}

    // 拷贝构造函数
    BSTree(const BSTree<K>& t) {
        _root = Copy(t._root); // 深拷贝。
    }

    // 赋值运算符重载
    BSTree<K>& operator=(BSTree<K> t) {
        swap(_root, t._root);
        return *this;
    }

    // 析构函数
    ~BSTree() {
        Destroy(_root);
        _root = nullptr;
    }

    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                return false;
            }
        }

        cur = new Node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        }
        else if (parent->_key > key) {
            parent->_left = cur;
        }

        return true;
    }

    // 打印树。
    void InOrder() {
        _InOrder(_root);
    }
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }

    bool Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                cur = cur->_left;
            }
            else {
                return true;
            }
        }

        return false;
    }

    bool erase(const K& key) {
        Node* parent = nullptr;
        Node* cur = _root;

        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }
            else {
                // 删除
                // 1.叶子节点 / 托孤
                // 左侧为空。
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    }
                    else {
                        if (parent->_left == cur) {
                            parent->_left = cur->_right;
                        }
                        else {
                            parent->_right = cur->_right;
                        }
                    }
                    delete cur;
                }/*右侧为空*/
                else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    }
                    else {
                        if (parent->_left == cur) {
                            parent->_left = cur->_left;
                        }
                        else {
                            parent->_right = cur->_left;
                        }
                    }
                    delete cur;
                } /*2.找左子树最大节点 / 右子树最小节点*/
                else {
                    Node* pminRight = cur;
                    Node* minRight = cur->_right;
                    while (minRight->_left) {
                        pminRight = minRight;
                        minRight = minRight->_left;
                    }
                    cur->_key = minRight->_key;
                    if (pminRight->_left == minRight)
                        pminRight->_left = minRight->_right;
                    else
                        pminRight->_right = minRight->_right;

                    delete minRight;
                }
                return true;
            }
        }

        return false;
    }
    
private:
    Node* Copy(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        Node* newRoot = new Node(root->_key);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

    void Destroy(Node*& root) {
        if (root == nullptr) {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
        root = nullptr;
    }

    Node* _root = nullptr;
};

附上一段测试样例

#include "BSTree.h"

int main() {
    int a[] = { 8, 3, 1, 10, 6, 4, 7, 14 ,13 };
    BSTree<int> t;
    for (auto e: a){
        t.Insert(e);
    }

    t.InOrder(); // 1 3 4 6 7 8 10 13 14 
    cout << endl;

    t.erase(7); // 删叶子节点。1 3 4 6 8 10 13 14 
    t.InOrder();
    cout << endl;
    t.erase(3); // 只有左孩子的节点。1 4 6 8 10 13 14 
    t.InOrder();
    cout << endl;
    t.erase(6); // 删有两个孩子的节点。1 4 8 10 13 14 
    t.InOrder();
    cout << endl;
    t.erase(8); // 删叶子节点。1 4 10 13 14 
    t.InOrder();
    cout << endl;

    return 0;
}

值得一提的是，对于一些接口，利用迭代可以使代码有所简化。

1. 插入

bool _InsertR(Node*& root, const K& x) {
        if (root == nullptr) {
            // 插入
            root = new Node(x);
            return true;
        } 
        
        else if (root->_key > x) {
            _InsertR(root->_left, x);
        }
        else if (root->_key < x) {
            _InsertR(root->_right, x);
        }
        else { return false; }
    }
bool InsertR(const K& x) {
        return _InsertR(_root, x);
    }

2. 删除

bool _EraseR(Node*& root, const K& x) {
        if (root == nullptr) {
            return false;
        }

        if (root->_key < x) {
            return _EraseR(root->_right, x);
        }
        else if (root->_key > x) {
            return _EraseR(root->_left, x);
        }
        else {
            Node* del = root;
            if (root->_left == nullptr) {
                root = root->_right;
            }
            else if (root->_right == nullptr) {
                root = root->_left;
            }
            else {
                Node* maxLeft = root->_left;
                while (maxLeft->_right) {
                    maxLeft = maxLeft->_right;
                }
                root->_key = maxLeft->_key;
                return _EraseR(root->_left, maxLeft->_key);
            }
            delete del;
            return true;
        }
    }

bool EraseR(const K& x) {
        return _EraseR(_root, x);
    }