今天重写了一遍二叉搜索树,在这里记录一下吧。

1.二分查找法定义

二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

2.二叉查找树(Binary Search Tree)基础

二叉查找树也可叫做二分查找树。
它不仅可以查找数据,还可以高效地插入、删除数据。
特点:每个节点的key值大于左子节点,小于右子节点。

注意它不一定是完全的二叉树。

二叉查找树有两个属性:

  • 所有节点都比左子树中的节点大
  • 所有节点都小于右子树中的节点

通过这两个属性,可以推断出以下结论:

  • 二叉查找树最小的节点位于最顶端节点的最左边子树行的末尾(如图数字 3 )
  • 二叉查找树的最大节点位于最顶端节点的最右边的子树行的末尾(如图数字 28 )

3.代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

struct Node
{
    int value;

    Node* parent = nullptr;
    Node* left = nullptr;
    Node* right = nullptr;

    Node(const int &v = 0) :value(v) {    };

    int operator * ()
    {
        return value;
    }
};

class BST
{
private:
    Node* root = nullptr;
    int SIZE = 0;

    /*查找节点前驱,后继*/
    Node* find_predecessor(Node* n);
    Node* find_successor(Node* n);

    /*插入,删除*/
    bool insert(Node* n);
    bool erase(Node* n);

    /*三序遍历*/
    void __preorderTraversal(Node* node, vector<int> &res);
    void __inorderTraversal(Node* node, vector<int> &res);
    void __postorderTraversal(Node* node, vector<int> &res);


public:
    /*构造,析构*/
    BST() :root(nullptr), SIZE(0) {        }
    BST(vector<int> data);
    ~BST();

    /*二叉搜索树的信息*/
    Node* begin() { return root; }
    bool empty() { return SIZE == 0; }
    int size() { return SIZE; }

    /*查找*/
    Node* find(const int &data);
    Node* find_predecessor(const int &v);//寻找前驱节点
    Node* find_successor(const int &v);//寻找后继节点

    /*插入,删除*/
    bool insert(const int &v);
    bool erase(const int &v);
    void clear();

    /*三序遍历*/
    vector<int> preorderTraversal(Node* node);
    vector<int> inorderTraversal(Node* node);
    vector<int> postorderTraversal(Node* node);


    /*其他*/
    void traversal(Node* node, void(*func)(int data) = [](int data)->void {cout << data << " "; });//遍历输出所有节点
};

BST::BST(vector<int> data)
{
    for (auto n : data)//C++11支持的冒号遍历
        insert(n);  //auto的作用是自动选择相应的类型

    return;
}

BST::~BST()
{
    clear();

    return;
}


/*****************************************************************
Function:find_predecessor
Description:查找节点的前驱。

节点x的前驱,就是指value小于x节点中value最大的那个节点
若x的左子树不为空,则x前驱是x节点左子树里最靠右的那个节点
如果x的左子树为空,那么我们就要向上找x的第一个有右孩子且左子树里没有
x节点的祖先。
*****************************************************************/

Node * BST::find_predecessor(const int & data)
{
    Node* tmp = find(data);

    return tmp == nullptr ? nullptr : find_predecessor(tmp);
}

Node * BST::find_predecessor(Node * n)
{
    Node* tmp = n;

    if (tmp->left != nullptr)
    {//当左子树不为空的时候
        tmp = tmp->left;

        while (tmp->right != nullptr)
            tmp = tmp->right;//寻找左子树中最右边的节点

        return tmp;
    }

    while (tmp->parent != nullptr && tmp->parent->left == tmp)
        tmp = tmp->parent;//找x的第一个有右孩子且左子树里没有x节点的祖先

    return tmp->parent;
}

/*****************************************************************
Function:find_predecessor
Description:查找节点的后继。

节点x的后继,就是指value大于x节点中value最小的那个节点
若x的右子树不为空,则x后继是x节点右子树里最靠左的那个节点
如果x的右子树为空,那么我们就要向上找x的第一个有左孩子且右子树里
没有x节点的祖先。
*****************************************************************/

Node * BST::find_successor(const int & data)
{
    Node* tmp = find(data);

    return tmp == nullptr ? nullptr : find_successor(data);
}

Node * BST::find_successor(Node * n)
{
    Node* tmp = n;

    if (tmp->right != nullptr)
    {
        tmp = tmp->right;

        while (tmp->left != nullptr)
            tmp = tmp->left;

        return tmp;
    }

    while (tmp->parent != nullptr && tmp->parent->right != tmp)
        tmp = tmp->parent;//向上找x的第一个有左孩子且右子树里没有x节点的祖先

    return tmp->parent;
}

/*****************************************************************
Function:find
Description:查找值为data的节点。
*****************************************************************/

Node * BST::find(const int & data)
{
    Node* tmp = root;

    while (tmp != nullptr && tmp->value != data)
        tmp = data > tmp->value ? tmp->right : tmp->left;

    return tmp;
}

/*****************************************************************
Function:insert
Description:向树中插入值data。

新插入的节点一定会取代一个原来的叶子节点,我们只要确定被取代的是
哪一个叶子节点就行了。
我们从根节点开始,利用二叉搜索树的性质比对值来向下查找,直到到达
最后的叶子节点,这个节点就是要用插入节点替换的叶子节点。
*****************************************************************/

bool BST::insert(const int & data)
{
    Node* tmp = new Node();
    return insert(tmp);
}

bool BST::insert(Node * n)
{
    Node* tmp = n;
    SIZE++;

    if (root == nullptr)
    {
        root = n;//如果根节点为空则直接插入
        return true;
    }

    while (true)//循环找出插入点
    {
        if (tmp->value > n->value)
        {//插入在左子树的情况
            if (tmp->left != nullptr)
                tmp = tmp->left;//左子树不为空则继续找
            else
            {
                tmp->left = n;//如果左子树为空则直接插入
                n->parent = tmp;//修改父节点为tmp指向的节点
                return true;
            }
        }
        else
        {//插入右子树的情况,同上
            if (tmp->right != nullptr)
                tmp = tmp->right;
            else
            {
                tmp->right = n;
                n->parent = tmp;
                return true;
            }
        }
    }

    return false;
}

/*****************************************************************
Function:erase
Description:从二叉树中删除node节点,返回删除是否成功。

删除的情况比插入复杂,一共有3种可能的情况。
1. 被删除的节点x没有nullptr节点以外的孩子节点时,直接删除,修改
父节点指针指向nullptr节点即可。
2. 被删除的节点x只有一个孩子时,用这个孩子节点替换被删除节点的位
置即可。
3. 被删除的节点x有两个孩子时,我们就要查找x节点的后继y节点,注意
y节点一定在x节点的右子树中而且y节点没有左孩子,此时,我们先用y节
点的右孩子代替y节点原先的位置,然后再用y节点代替x节点位置即可完
成删除操作。
*****************************************************************/

bool BST::erase(Node * n)
{
    if (n == nullptr)
        return false;

    SIZE--;
    Node* tmp = n;

    if (n->left == nullptr && n->right == nullptr)//没有子节点
        tmp = nullptr;
    else if (n->left == nullptr || n->right == nullptr)
    {//一个子节点
        tmp = n->left == nullptr ? n->right : n->left;
        tmp->parent = n->parent;
        /*因为tmp要取代n,所以tmp要完全复制n的信息。
        又因tmp是n的一个子节点,故只需复制n的parent就够了*/
    }
    else//有两个子节点
    {
        tmp = find_successor(n);//用n节点的后继y来取代n
        Node* successor_right;
        //后继y可能有右儿子,所以需要先用y的右儿子取代y,再让y取代n

        if (tmp->right == nullptr)//没有右儿子的话就用nullptr来取代y
            successor_right = nullptr;
        else
        {
            successor_right = tmp->right;
            successor_right->parent = tmp->parent;//用y的右儿子取代y
        }

        /* 这里用来修改y的父节点,使y的右儿子完全取代y */
        if (tmp->parent->left == tmp)
            tmp->parent->left = successor_right;
        else
            tmp->parent->right = successor_right;

        /* 至此,对y的处理就已经完成了。接下来就是让y取代n了
        这一步只需要把y的值赋值给n,然后删除y就好了 */

        n->value = tmp->value;
        delete tmp;

        return true;
    }

    /* 情况一和情况二到此为止取代n节点的tmp已经确定,而且当tmp不是
    nullptr的时候,tmp也已经复制了必要的n的属性,剩下的就是让n的
    父节点指向tmp了

    注意被删除的节点有可能是根节点,所以当我们发现被删除的是根节点
    时,不需要让n的父节点指向tmp,因为n没有父节点了,但是这个时候
    必须修改root指针的指向 */

    if (n->parent != nullptr)
    {
        if (n->parent->left == tmp)
            n->parent->left = tmp;
        else
            n->parent->right = tmp;
    }
    else
        root = tmp;

    delete n;

    return true;
}

bool BST::erase(const int & data)
{
    return erase(find(data));
}

/*****************************************************************
Function:clear
Description:清空树。
*****************************************************************/

void BST::clear()
{//这里我用了广搜的思想,也可以使用递归
    if (root == nullptr)
        return;

    queue<Node*> q;

    q.push(root);

    while (!q.empty())
    {
        Node* tmp = q.front();
        q.pop();

        if (tmp->left != nullptr)
            q.push(tmp->left);

        if (tmp->right != nullptr)
            q.push(tmp->right);

        delete tmp;

        SIZE--;
    }

    root = nullptr;

    return;
}

/*****************************************************************
Function:traversal
Description:遍历输出二叉搜索树。

这里解释一下这个lambda语法:
第一个参数是为了进行递归而设立的。
第二个参数是一个函数指针,这个函数指针指向一个没有返回值同时有一个int类型参数
的函数,
并且我用lambda表达式给这个函数指针赋了一个默认值,这个默认函数的功能是输出参
数k,用来遍历输出每一个节点的值,
大家可以用别的lambda表达式或者函数来覆盖这个默认值,以达到定制功能的目的
*****************************************************************/

void BST::traversal(Node* node, void(*func)(int data))
{
    if (node = nullptr)
        return;

    traversal(node->left);
    func(node->value);
    traversal(node->right);

    return;
}

/*****************************************************************
Function:preorderTraversal
Description:前序遍历。
*****************************************************************/

void BST::__preorderTraversal(Node* node, vector<int> &res)
{
    if (node)
    {
        res.push_back(node->value);
        __preorderTraversal(node->left, res);
        __preorderTraversal(node->right, res);
    }

    return;
}

vector<int> BST::preorderTraversal(Node* node)
{
    vector<int> res;
    __preorderTraversal(node, res);
    return res;
}

/*****************************************************************
Function:inorderTraversal
Description:中序遍历。
*****************************************************************/

void BST::__inorderTraversal(Node* node, vector<int> &res)
{
    if (node)
    {
        __inorderTraversal(node->left, res);
        res.push_back(node->value);
        __inorderTraversal(node->right, res);
    }

    return;
}

vector<int> BST::inorderTraversal(Node* node)
{
    vector<int> res;
    __inorderTraversal(node, res);
    return res;
}

/*****************************************************************
Function:postorderTraversal
Description:后序遍历。
*****************************************************************/

void BST::__postorderTraversal(Node* node, vector<int> &res)
{
    if (node)
    {
        __postorderTraversal(node->left, res);
        __postorderTraversal(node->right, res);
        res.push_back(node->value);
    }

    return;
}

vector<int> BST::postorderTraversal(Node* node)
{
    vector<int> res;
    __postorderTraversal(node, res);
    return res;
}
Last modification:April 10th, 2019 at 04:43 pm
If you think my article is useful to you, please feel free to appreciate