BST树 | 我等春雷 来提醒你爱谁
Cobb 612 1

BST树

简单的理论 BST树 |  我等春雷 来提醒你爱谁 /* 有序关联容器 => 红黑树 RB BST:二叉排序树/二叉搜索树: 树要么为NULL;;要么每个节点的值 > 左子树所有节点的值;;要么每个节点的值 < 右子树所有节点的值, AVL:平衡二叉树 RB:红黑树 */

插入元素

BST树 |  我等春雷 来提醒你爱谁

// 前驱节点: 左子树中值最大的节点
// 后继节点: 右子树中值最小的节点
struct BSTNode
{
    BSTNode(int data = 0) :data_(data) {}
    int data_;
    BSTNode* left_{nullptr};
    BSTNode* right_{nullptr};
};

class BSTree
{
public:
    BSTree() :root_(nullptr) {}
    // 向BST树插入一个元素
    void emplace(int key)
    {
        BSTNode* p = new BSTNode(key);

        if (this->root_ == nullptr)
        {
            root_ = p;
            return;
        }

        BSTNode* cur = root_;
        BSTNode* parent = nullptr;
        while (cur != nullptr)
        {
            parent = cur;
            if (cur->data_ > key)
            {
                cur = cur->left_;
            }
            else if (cur->data_ < key)
            {
                cur = cur->right_;
            }
            else
            {
                return;
            }
        }

        // p => 查到父节点parent里面
        if (parent->data_ > key)
        {
            parent->left_ = p;
        }
        else
        {
            parent->right_ = p;
        }
    }

查询元素

BST树 |  我等春雷 来提醒你爱谁


    // 查询
    bool find(int key)
    {
        if (this->root_ == nullptr)
            return false;

        BSTNode* cur = root_;
        while (cur != nullptr)
        {
            if (cur->data_ > key)
            {
                cur = cur->left_;
            }
            else if (cur->data_ < key)
            {
                cur = cur->right_;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

删除元素

BST树 |  我等春雷 来提醒你爱谁


    // 删除
    void erase(int key)
    {
        BSTNode* parent = nullptr;
        BSTNode* cur = root_;
        while (cur != nullptr)
        {
            if (cur->data_ > key)
            {
                parent = cur;
                cur = cur->left_;
            }
            else if (cur->data_ < key)
            {
                parent = cur;
                cur = cur->right_;
            }
            else
            {
                break;
            }
        }

        if (cur == nullptr)
            return;

        // 处理情况3
        if (cur->left_ != nullptr && cur->right_ != nullptr)
        {
            BSTNode* old = cur;

            parent = cur;
            cur = cur->left_;
            while (cur->right_ != nullptr)
            {
                parent = cur;
                cur = cur->right_;
            }

            // cur就指向前驱节点了
            old->data_ = cur->data_;
        }

        // 情况1和情况2
        BSTNode* child = cur->left_;
        if (child == nullptr)
            child = cur->right_;

        // child为nullptr或者指向了cur那个唯一的孩子
        if (parent == nullptr)
        {
            // 删除根节点了
            root_ = child;
        }
        else if (parent->left_ == cur)
        {
            parent->left_ = child;
        }
        else
        {
            parent->right_ = child;
        }

        delete cur;
    }

前序遍历(VLR)

BST树 |  我等春雷 来提醒你爱谁

 // 递归实现
 void preOrder(BSTNode* node) // 遍历node节点的
    {
        if (node == nullptr)
            return;
        // VLR
        cout << node->data_ << " "; // 访问V节点
        preOrder(node->left_);      // L
        preOrder(node->right_);     // R
    }

 // 非递归实现前序遍历  VLR
    void non_preOrder()
    {
        stack<BSTNode*> s;
        s.push(root_);

        while (!s.empty())
        {
            BSTNode* n = s.top();
            s.pop();
            cout << n->data_ << " ";  // V

            if (n->left_ != nullptr)  // L
                s.push(n->left_);
            if (n->right_ != nullptr) // R
                s.push(n->right_);
        }
        cout << endl;
    }

中序遍历

BST树 |  我等春雷 来提醒你爱谁

// 递归实现,只考虑水平的逻辑。、本身调用是垂直的。
 void inOrder(BSTNode* node)
    {
        // LVR
        if (node == nullptr)
            return;

        inOrder(node->left_);       // L
        cout << node->data_ << " "; // V
        inOrder(node->right_);      // R
    }


 // 非递归实现中序遍历
    void non_inOrder()
    {
        stack<BSTNode*> s;
        BSTNode* cur = root_;

        while (!s.empty() || cur != nullptr)
        {
            if (cur != nullptr)
            {
                s.push(cur);
                cur = cur->left_;  // L
            }
            else
            {
                cur = s.top();    // v
                s.pop();

                cout << cur->data_ << " ";
                cur = cur->right_;  // R
            }
        }
        cout << endl;

        /*stack<BSTNode*> s;
        BSTNode* cur = root_;
        while (cur != nullptr)
        {
            s.push(cur);
            cur = cur->left_;
        }

        while (!s.empty())
        {
            cur = s.top();
            s.pop();

            cout << cur->data_ << " ";

            cur = cur->right_;
            while (cur != nullptr)
            {
                s.push(cur);
                cur = cur->left_;
            }
        }*/
    }


后序遍历

BST树 |  我等春雷 来提醒你爱谁

//递归实现
    void postOrder(BSTNode* node)
    {
        // LVR
        if (node == nullptr)
            return;

        postOrder(node->left_);      // L
        postOrder(node->right_);     // R
        cout << node->data_ << " ";  // V
    }



 // 非递归实现后序遍历
    void non_postOrder()
    {
        // LRV  => VRL
        stack<BSTNode*> bs;
        stack<BSTNode*> s;
        s.push(root_);

        while (!s.empty())
        {
            BSTNode* n = s.top();
            s.pop();
            bs.push(n);

            if (n->right_ != nullptr) // R
                s.push(n->right_);
            if (n->left_ != nullptr)  // L
                s.push(n->left_);
        }

        while (!bs.empty())
        {
            cout << bs.top()->data_ << " ";
            bs.pop();
        }
        cout << endl;
    }

private:
    BSTNode* root_; // 指向BST树的root根节点
};

测试代码

int main()
{
    srand(time(0));

    for (int i = 0; i < 10; i++)
    {
        cout << rand() % 100 << " ";
    }

    BSTree bst;
    bst.emplace(53);
    bst.emplace(30);
    bst.emplace(42);
    bst.emplace(25);
    bst.emplace(70);
    bst.emplace(68);
    bst.emplace(92);
    bst.emplace(60);
    bst.emplace(69);

    bst.preOrder();
    bst.non_preOrder();
    bst.inOrder();
    bst.non_inOrder();
    bst.postOrder();
    bst.non_postOrder();


    //bst.erase(70);

    cout << endl;

    cout << "--------------" << endl;
    set<int> s{ 12,5,67,8,90,32,54,21,87 }; 
    for (int v : s)  // 中序遍历红黑树
    {
        cout << v << " ";
    }
    cout << endl;
}

4种节点旋转

BST树 |  我等春雷 来提醒你爱谁

1-10节点旋转示例

BST树 |  我等春雷 来提醒你爱谁 BST树 |  我等春雷 来提醒你爱谁

接口

BST树 |  我等春雷 来提醒你爱谁

二叉树的节点类型

// 二叉树的节点类型
struct Node
{
    Node(int data) : data_(data), left_(nullptr), right_(nullptr) {}
    int data_;
    Node* left_;
    Node* right_;
};

计算二叉树节点的总个数

// 计算二叉树节点的总个数
int Number(Node* root)
{
    if (root == nullptr)
    {
        return 0;
    }
    return Number(root->left_) +
        Number(root->right_) + 1;
}

二叉树的层高

// 二叉树的层高
int Hight(Node* root)
{
    if (root == nullptr)
    {
        return 0;
    }
    int a = Hight(root->left_);
    int b = Hight(root->right_);
    return a > b ? a + 1 : b + 1;
}

求最近公共祖先节点的值

// 求最近公共祖先节点的值
int LCA(Node* root, int v1, int v2)
{
    if (root == nullptr)
    {
        return -1;
    }

    if (root->data_ > v1 && root->data_ > v2)
    {
        return LCA(root->left_, v1, v2);
    }
    else if (root->data_ < v1 && root->data_ < v2)
    {
        return LCA(root->right_, v1, v2);
    }
    else
    {
        return root->data_;
    }
}

判断一颗二叉树是不是BST树

// 判断一颗二叉树是不是BST树 是BST返回true,否则返回false
// 左孩子 < 当前节点 < 右孩子 
Node* pre = nullptr;
bool IsBSTree(Node* root)
{
    if (root == nullptr)
    {
        return true;
    }

    // 左子树不是BST树
    if (!IsBSTree(root->left_))  // L
    {
        return false;
    }

    // root 判断当前节点和上一个节点的值的大小关系 
    // pre指向上一个输出的节点,root指向当前输出的节点
    // pre如果为空,让pre指向根节点
    if (pre != nullptr && pre->data_ > root->data_) // V
    {
        return false;
    }
    pre = root;

    return IsBSTree(root->right_);  // R
}

判断二叉树是不是平衡树


// 判断二叉树是不是平衡树,任意节点的左右子树高度差不超过1
bool IsBalanceTree(Node* root)
{
    if (root == nullptr)
    {
        return true;
    }
    // 先判断 左/右 子树是否为平衡树
    if (!IsBalanceTree(root->left_))
    {
        return false;
    }
    if (!IsBalanceTree(root->right_))
    {
        return false;
    }

    // 层高
    int a = Hight(root->left_);
    int b = Hight(root->right_);
    if (abs(a - b) > 1)
    {
        return false;
    }
    else
    {
        return true;
    }
}

输出bst树中第k大的元素值

// 输出bst树中第k大的元素值
int FindValue(Node* root, int k)
{
    if (root == nullptr)
    {
        return -1;
    }
    static int a = 0;
    // RVL
    int v = FindValue(root->right_, k); //R
    if (v != -1)
    {
        return v;
    }

    a++;  // 做标记,递归到第K个数,返回值就行
    if (a == k)  
    {
        return root->data_;   // V
    }

    // 右边没找到,到左边来找
    return FindValue(root->left_, k);   // L
}

判断root2是否是root1的子树

// 判断root2是否是root1的子树
bool IsChildTree_(Node* root1, Node* root2)
{
    if (root1 == nullptr && root2 == nullptr)
        return true;
    if (root1 == nullptr)
        return false;
    if (root2 == nullptr)
        return true;

    if (root1->data_ != root2->data_)
        return false;

    // 判断左右子树是否相同
    return IsChildTree_(root1->left_, root2->left_) &&
        IsChildTree_(root1->right_, root2->right_);
}


bool IsChildTree(Node* root1, Node* root2)
{
    // 在大树里面搜索小树的根节点是否存在
    while (root1 != nullptr)
    {
        if (root1->data_ == root2->data_)
        {
            break;
        }
        else if (root1->data_ > root2->data_)
        {
            root1 = root1->left_;
        }
        else
        {
            root1 = root1->right_;
        }
    }

    if (root1 == nullptr)
        return false;

    return IsChildTree_(root1, root2);
}

测试代码


int main()
{
    Node root(50);
    Node n1(35);
    Node n2(20);
    Node n3(45);
    Node n4(80);
    Node n5(70);
    Node n6(75);
    Node n7(90);
    Node n8(85);

    root.left_ = &n1;
    root.right_ = &n4;
    n1.left_ = &n2;
    n1.right_ = &n3;
    n4.left_ = &n5;
    n4.right_ = &n7;
    n5.right_ = &n6;
    n7.left_ = &n8;

    Node root2(35);
    root2.left_ = &n2;
    root2.right_ = &n3;

    //InOrder(&root);
    //cout << endl;
    bool a = IsChildTree(&root, &root2);
    cout << a << endl;
    return 0;
}

评论区

索引目录