二叉搜索树中序后代-ag捕鱼王app官网

当前位置：ag捕鱼王app官网 > > 算法 >

二叉搜索树中序后代

作者：迹忆客最近更新：2023/03/20 浏览次数：

二叉树的中序后代是二叉树中序遍历中下一个节点。所以，对于树内的最后一个节点来说，它是 null。由于二叉搜索树的中序遍历是一个排序数组。比给定节点大键最小的节点被定义为它的中序后代。在 bst 中，中序后代有两种可能，即在节点的右侧子树或祖先中，值最小的节点。否则，该节点的中序后代不存在。

bst 算法中的中序后代算法

如果 root=null，则将 succ 设为 null 并返回。
如果 root->data<current->data，则 succ 为 current，current 为 current->left。
如果 root->data>current->data，则 current 为 current->right。
如果 root->data == current->data 和 root->right != null, succ = minimum(current->right)。
返回 succ。

bst 中的中序后代图示

3 的中序后代是 4，因为 3 有一个右结点，4 是右子树中比 3 大的最小的结点。

4 的顺序后代是 5，因为 4 没有右结点，我们要看它的祖先，其中 5 是比 4 大的最小的结点。

bst 中序后代的实现

#include using namespace std;
class node {
public:
    int data;
    node *left, *right;
    node(int x) {
        this->data = x;
        this->left = this->right = null;
    }
};
node* insert(node* root, int key)
{
    if (root == null) {
        return new node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    }
    else {
        root->right = insert(root->right, key);
    }
    return root;
}
node* getnextleft(node* root)
{
    while (root->left) {
        root = root->left;
    }
    return root;
}
void inordersuccessor(node* root, node*& succ, int key)
{
    if (root == null) {
        succ = null;
        return;
    }
    if (root->data == key)
    {
        if (root->right) {
            succ = getnextleft(root->right);
        }
    }
    else if (key < root->data)
    {
        succ = root;
        inordersuccessor(root->left, succ, key);
    }
    else {
        inordersuccessor(root->right, succ, key);
    }
}
int main()
{
    int keys[] = { 1, 5, 8, 2, 6, 3, 7, 4 };
    node* root = null;
    for (int key : keys) {
        root = insert(root, key);
    }
    for (int key : keys)
    {
        node* prec = null;
        inordersuccessor(root, prec, key);
        if (prec) {
            cout << "inorder successor of node " << key << " is " << prec->data;
        }
        else {
            cout << "no inorder successor of node " << key;
        }
        cout << '\n';
    }
    return 0;
}

bst 查找中序后代的算法复杂度

时间复杂度

平均情况

在平均情况下，在 bst 中寻找中序后代的时间复杂度与二叉搜索树的高度相当。平均来说，一个 bst 的高度是 o(logn)。当形成的 bst 是一个平衡的 bst 时，就会出现这种情况。因此，时间复杂度是 [big theta]：o(logn)。

最佳情况

最好的情况是当树是一个平衡的 bst 时。最佳情况下，删除的时间复杂度为 o(logn)。它与平均情况下的时间复杂度相同。

最坏情况

在最坏的情况下，我们可能需要从根节点到最深的叶子节点，即树的整个高度 h。如果树是不平衡的，即它是倾斜的，树的高度可能会变成 n，因此插入和搜索操作的最坏情况下的时间复杂性是 o(n)。

空间复杂度

由于递归调用所需的额外空间，该算法的空间复杂度为 o(h)。

下一篇：将二叉树转换为二叉搜索树

转载请发邮件至 1244347461@qq.com 进行申请，经作者同意之后，转载请以链接形式注明出处

本文地址：

将二叉树转换为二叉搜索树

发布时间：2023/03/20 浏览次数：185 分类：算法

本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多有两个子节点。这些子节点被称为左子和右子。

发布时间：2023/03/20 浏览次数：189 分类：算法

本教程介绍了二叉搜索树的删除操作。

发布时间：2023/03/20 浏览次数：232 分类：算法

本教程介绍了二叉树上的树遍历中序遍历、前序遍历和后序遍历。

循环双向链表

发布时间：2023/03/20 浏览次数：169 分类：算法

本教程介绍了循环双向链表的数据结构。

循环链接列表

发布时间：2023/03/20 浏览次数：203 分类：算法

本教程介绍了循环链接列表的数据结构。

发布时间：2023/03/20 浏览次数：104 分类：算法

本教程介绍了双向链接列表的数据结构。

二叉搜索树中序后代-ag捕鱼王app官网