二叉樹（三）二叉查找樹

二叉查找樹（二叉搜索樹、二叉排序樹）的創建、增、刪、查、改。

main.cpp：

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

int main()
{
    BinarySearchTree<int> bst{ 5,1,3,5,6,6,8,2,4,8,9,0,3,1,7 };
    auto il = { 1,2,3,4,5,6 };

    bst.insert(il.begin(), il.end());
    cout << "datas: ";
    bst.show();
    cout << endl;
    cout << "size: " << bst.size() << endl;
    cout << "level: " << bst.level() << endl << endl;
    cout << "after erase 6: " << endl;
    cout << "erased: " << bst.erase(6) << " node(s)" << endl;
    cout << "datas: ";
    bst.show();
    cout << endl;
    cout << "size: " << bst.size() << endl;
    cout << "level: " << bst.level() << endl;

    return 0;
}

BinarySearchTree.h：

#pragma once
#ifndef __BINARYSEARCHTREE_H__
#define __BINARYSEARCHTREE_H__


#include <queue>
#include <initializer_list>
template<typename _Ty>
class BinarySearchTree
{
private:
    struct Node
    {
        _Ty key;
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
        Node(const _Ty& _key) :key(_key) {}
    };

public:
    BinarySearchTree() = default;
    template<typename _Iter>
    BinarySearchTree(_Iter, _Iter);
    BinarySearchTree(const std::initializer_list<_Ty>&);
    BinarySearchTree(const BinarySearchTree<_Ty>&);
    BinarySearchTree(BinarySearchTree<_Ty>&&) noexcept;

    ~BinarySearchTree() { clear(root); }
    void clear() { clear(root); }
    bool empty() const { return size_n == 0; }
    size_t size() const { return size_n; }
    void show() const { show(root); }
    size_t level() const;

    void swap(BinarySearchTree<_Ty>&);
    void insert(const _Ty&);
    template<typename _Iter>
    void insert(_Iter, _Iter);
    size_t erase(const _Ty&);
    void erase(Node*);

    Node* find(const _Ty& _key) const { return find(root, _key); }
    Node* iterative_find(const _Ty& _key) const { return iterative_find(root, _key); }
    Node* maximum() const { return maximum(root); }
    Node* minimum() const { return minimum(root); }
    Node* predecessor() const { return predecessor(root); }
    Node* successor() const { return successor(root); }

private:
    void copy(Node*);
    void clear(Node*&);
    void show(Node*) const;
    Node* find(Node*, const _Ty&) const;
    Node* iterative_find(Node*, const _Ty&) const;
    Node* maximum(Node*) const;
    Node* minimum(Node*) const;
    Node* predecessor(Node*) const;
    Node* successor(Node*) const;

private:
    size_t size_n = 0;
    Node* root = nullptr;
};

template<typename _Ty>
template<typename _Iter>
BinarySearchTree<_Ty>::BinarySearchTree(_Iter _it1, _Iter _it2)
{
    while (_it1 != _it2)
    {
        insert(*_it1);
        ++_it1;
    }
}

template<typename _Ty>
BinarySearchTree<_Ty>::BinarySearchTree(const std::initializer_list<_Ty>& _il)
{
    for (const auto& key : _il) insert(key);
}

template<typename _Ty>
BinarySearchTree<_Ty>::BinarySearchTree(const BinarySearchTree<_Ty>& _right)
{
    copy(_right.getRoot());
}

template<typename _Ty>
BinarySearchTree<_Ty>::BinarySearchTree(BinarySearchTree<_Ty>&& _right) noexcept
{
    root = _right.root;
    size_n = _right.size_n;
    _right.root = nullptr;
    _right.size_n = 0;
}

template<typename _Ty>
size_t BinarySearchTree<_Ty>::level() const
{
    if (root == nullptr) 0;
    size_t n = 0;
    std::queue<Node*> nodePointers;
    nodePointers.push(root);
    while (!nodePointers.empty())
    {
        Node* levelBegin = nodePointers.front();
        Node* levelEnd = nodePointers.back();
        Node* cur = levelBegin;
        while (true)
        {
            if (cur->left != nullptr) nodePointers.push(cur->left);
            if (cur->right != nullptr) nodePointers.push(cur->right);
            if (cur == levelEnd)
                break;
            nodePointers.pop();
            cur = nodePointers.front();
        }
        nodePointers.pop();
        ++n;
    }
    return n;
}

template<typename _Ty>
void BinarySearchTree<_Ty>::copy(Node* _node)
{
    if (_node == nullptr) return;
    insert(_node->key);
    copy(_node->left);
    copy(_node->right);
}

template<typename _Ty>
void BinarySearchTree<_Ty>::clear(Node*& _node)
{
    if (_node == nullptr) return;
    clear(_node->left);
    clear(_node->right);
    delete _node;
    _node = nullptr;
    --size_n;
}

template<typename _Ty>
void BinarySearchTree<_Ty>::show(Node* _node) const
{
    if (_node == nullptr) return;
    show(_node->left);
    std::cout << _node->key << " ";
    show(_node->right);
}

template<typename _Ty>
void BinarySearchTree<_Ty>::swap(BinarySearchTree<_Ty>& _right)
{
    std::swap(root, _right->root);
    std::swap(size_n, _right->size_n);
}

template<typename _Ty>
void BinarySearchTree<_Ty>::insert(const _Ty& _key)
{
    ++size_n;
    if (root == nullptr)
    {
        root = new Node(_key);
        return;
    }
    Node* temp = root;
    while (true)
    {
        if (_key < temp->key && temp->left != nullptr)
            temp = temp->left;
        else if (_key < temp->key && temp->left == nullptr)
            break;
        else if (_key >= temp->key && temp->right != nullptr)
            temp = temp->right;
        else
            break;
    }
    Node* newNode = new Node(_key);
    newNode->parent = temp;
    if (_key < temp->key) temp->left = newNode;
    else temp->right = newNode;
}

template<typename _Ty>
template<typename _Iter>
void BinarySearchTree<_Ty>::insert(_Iter _it1, _Iter _it2)
{
    while (_it1 != _it2)
    {
        insert(*_it1);
        ++_it1;
    }
}

template<typename _Ty>
size_t BinarySearchTree<_Ty>::erase(const _Ty& _key)
{
    size_t n = 0;
    Node* del = find(_key);
    while (del != nullptr)
    {
        ++n;
        erase(del);
        del = find(_key);
    }
    return n;
}

template<typename _Ty>
void BinarySearchTree<_Ty>::erase(Node* _node)
{
    if (_node == nullptr) return;
    if (_node == root)
    {
        if (_node->right != nullptr)
        {
            Node* min = minimum(_node->right);
            min->left = _node->left;
            root = _node->right;
        }
        else
            root = _node->left;
        root->parent = nullptr;
        delete _node;
        return;
    }
    Node* par = _node->parent;
    if (_node->left == nullptr && _node->right == nullptr)
    {
        if (par->left == _node)
            par->left = nullptr;
        else
            par->right = nullptr;
    }
    else
    {
        if (_node->right != nullptr)
        {
            if (_node->left != nullptr)
            {
                Node* min = minimum(_node->right);
                min->left = _node->left;
            }
            _node->right->parent = par;
            if (par->left == _node)
                par->left = _node->right;
            else
                par->right = _node->right;
        }
        else
        {
            if (_node->left != nullptr)
                _node->left->parent = par;
            if (par->left == _node)
                par->left = _node->left;
            else
                par->right = _node->left;
        }
    }
    delete _node;
    --size_n;
}

template<typename _Ty>
typename BinarySearchTree<_Ty>::Node* BinarySearchTree<_Ty>::find(Node* _node, const _Ty& _key) const
{
    if (_node == nullptr || _node->key == _key)
        return _node;
    if (_key < _node->key)
        return find(_node->left, _key);
    else
        return find(_node->right, _key);
}

template<typename _Ty>
typename BinarySearchTree<_Ty>::Node* BinarySearchTree<_Ty>::iterative_find(Node* _node, const _Ty& _key) const
{
    while (_node != nullptr && _node->key != _key)
    {
        if (_key < _node->key)
            _node = _node->left;
        else
            _node = _node->right;
    }
    return _node;
}

template<typename _Ty>
typename BinarySearchTree<_Ty>::Node* BinarySearchTree<_Ty>::maximum(Node* _node) const
{

    if (_node == nullptr) return _node;
    while (_node->right != nullptr)
        _node = _node->right;
    return _node;
}

template<typename _Ty>
typename BinarySearchTree<_Ty>::Node* BinarySearchTree<_Ty>::minimum(Node* _node) const
{
    if (_node == nullptr) return _node;
    while (_node->left != nullptr)
        _node = _node->left;
    return _node;
}

template<typename _Ty>
typename BinarySearchTree<_Ty>::Node* BinarySearchTree<_Ty>::predecessor(Node* _node) const
{
    if (_node->left != nullptr)
        return maximum(_node->left);
    Node* par = _node->parent;
    while ((par != nullptr) && (_node == par->left))
    {
        _node = par;
        par = par->parent;
    }
    return par;
}

template<typename _Ty>
typename BinarySearchTree<_Ty>::Node* BinarySearchTree<_Ty>::successor(Node* _node) const
{
    if (_node->right != nullptr)
        return minimum(_node->left);
    Node* par = _node->parent;
    while ((par != nullptr) && (_node == par->right))
    {
        _node = par;
        par = par->parent;
    }
    return par;
}


#endif // !__BINARYSEARCHTREE_H__