C++从入门到精通：二叉搜索树

@toc

很多小伙伴为了刷题发愁
今天为大家推荐一款刷题神奇哦：刷题面试神器牛客
各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题应有尽有，赶快来装备自己吧！助你面试稳操胜券，solo全场面试官

一：二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
- 例：

在这里插入图片描述

int a [] = {5,3,4,1,7,8,2,6,0,9};

二：二叉搜索树实现

节点的定义

template <class K> //模板
class TreeNode
{
public:
    TreeNode<K>* _left;
    TreeNode<K>* _right;
    K _key;
    TreeNode(const K & key)
        :_left(nullptr),
        _right(nullptr),
        _key(key)
    {}
};

二叉搜索树实现

代码：

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

template <class K>
class TreeNode
{
public:
    TreeNode<K>* _left;
    TreeNode<K>* _right;
    K _key;
    TreeNode(const K & key)
        :_left(nullptr),
        _right(nullptr),
        _key(key)
    {}
};

template <class K>
class BSTree
{
    typedef TreeNode<K> Node;
private:
    Node* _FindR(Node* root, const K& key)
    {
        if (root == nullptr)
            return nullptr;

        if (root->_key > key)
        {
            return _FindR(_root->_left, key);
        }
        else if (root->_key < key)
        {
            return _FindR(_root->_right, key);
        }
        else
        {
            return _root;
        }
    }
    bool _insertR(Node*& root, const K& key) //递归版本,注意传引用
    { 
        if (root == nullptr)
        {
            root = new Node(key);
            return true;
        }
        if (root->_key > key)
        {
            return _FindR(_root->_left, key);
        }
        else if (root->_key < key)
        {
            return _FindR(_root->_right, key);
        }
        else
        {
            return false;
        }
    }
    bool _EraseR(Node*& root, const K& key)
    {
        if (root == nullptr)
        {
            return false;
        }
        if (root->_key > key)
        {
            return _EraseR(_root->_left, key);
        }
        else if (root->_key < key)
        {
            return _EraseR(_root->_right, key);
        }
        else //找到了
        {
            if (root->_left == nullptr) //假如左子树为空，直接等于右子树
                {
                Node* tem = root;
                root = root->_right;
                    delete tem;
                }
                else if (root->_right == nullptr)//假如右子树为空，root直接等于左子树
                {
                Node* tem = root;
                root = root->_left;
                    delete tem;
                }
                else  //左右子树都不为空时，1.先找到右边最小值  2.再保留最小值  3.递归去删除最小值   4.将最小值赋值给root
                {
                    Node* right = root->_right;
                    while (right->_left)
                    {
                        right = right->_left;
                    }
                    K temkey = right->_key;
                    _EraseR(right,right->_key);
                    root->_key = temkey;
                }
                return true;
        }
    }
    void _Destroy(Node* root)  //后序销毁
    {
        if (root == nullptr)
            return;
        _Destroy(root->_left);
        _Destroy(root->_right);
        delete root;
    }
    Node*  _BSTree(const Node*& root) //深拷贝一个树
    {
        if (root == nullptr)
            return nullptr;
        Node* cur = new Node(root->_key);
        cur->_left = _BSTree(root->_left);
        cur->_right = _BSTree(root->_right);
        return cur;
    }
public:
    BSTree()
        :_root(nullptr)
    {}
    ~BSTree()
    {
        _Destroy(_root);
    }
    BSTree(const BSTree<K>& a)
    {
        _root=_BSTree(a._root);
    }
    BSTree<K>& a operator=(const BSTree<K> a)
    {
        swap(_root, a._root);
        return *this;
    }
    bool insertR(const K& key) //递归版本
    {
        return _insertR(_root,key);
    }
    Node* FindR(const K& key)
    {
        return _FindR(_root, key);
    }
    bool EraseR(const K& key)
    {
        return _EraseR(_root,key);
    }
    bool insert(const K& key) //插入一个值
    {
        if (_root == nullptr) //为空时，直接构造一个
        {
            _root = new Node(key);
            return true;
        }
        else //不为空时，利用搜索数的特性找到该插入的位置
        {
            Node* cur = _root;
            Node* parent = _root;
            while (cur)
            {
                if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    return false; //搜索二叉树不允许有重复的数
                }
            }
            //循环走完，已经找到了
            cur = new Node(key);
            if (parent->_key > key)
            {
                parent->_left = cur;
            }
            else
            {
                parent->_right = cur;
            }

            return true;
        }
    }

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

    bool Erase(const K& key)
    {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_key > key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right; 
            }
            else // 找到了
            {
                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;
                }
                else
                {
                    Node* right = cur->_right;
                    while (right->_left)
                    {
                        right = right->_left;
                    }
                    K temkey = right->_key;
                    Erase(right->_key);
                    cur->_key = temkey;
                }
                return true;
            }
        }
        return false;
    }

    void PrintIoder()
    {
        Print(_root);
        cout << endl;
    }
    void Print(Node* root)
    {
        if (root == nullptr)
            return;

        Print(root->_left);
        cout << root->_key << " ";
        Print(root->_right);
    }
private:
    Node* _root;
};