将二叉树转换为二叉搜索树-ag捕鱼王app官网

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

web前端编程语言网络算法操作系统数据库

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

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

二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多有两个子节点。这些子节点被称为左子和右子。它也可以解释为一个不定向图，其中最上面的节点称为根。二叉搜索树(bst)是一种具有特殊属性的二叉树，它有助于以排序的方式保持数据的组织。

在本文中，我们将讨论如何将二叉树转换为二叉搜索树，同时保持二叉树的原始结构。

将二叉树转换为二叉搜索树的算法

创建一个名为 arr 的数组来存储二叉树节点的顺序遍历。
使用任何排序算法（合并排序 o(nlogn)、快速排序 o(n^2)、插入排序 o(n^2)等）对 arr 进行排序。
再次对树进行顺序遍历，并将排序数组 arr 中的元素存储在二叉树中，得出 bst。

二叉树转换为 bst 图解

二叉树到 bst 图解

我们在根节点 4 上调用顺序遍历。递归向左遍历到达节点 1，它是最左的节点，并将其包含在我们的输出中；由于它是根节点，没有左节点，我们回溯到节点 2，并将其包含在我们的遍历中。这样，我们遍历整棵树，并将按顺序遍历的结果以 [1，2，3，5，4，6] 的形式存储在数组 arr 中。
使用任意排序算法对数组 arr 进行排序，得到 [1，2，3，4，5，6]。
我们再次调用顺序遍历，将排序后的数组 arr 存储回二叉树中，得到我们的 bst。

二叉树转换为二叉搜索树的实现

#include using namespace std;
class node {
    public:
        int data;
        node *left, *right;
        node(int x) {
            this->data = x;
            this->left = this->right = null;
        }
};
vector<int>v;
void inorder(node *root) {
    if (root != null)
    {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}
void storetree(node*root, int i = 0) {
    if (!root) {
        return;
    }
    storetree(root->left);
    v.push_back(root->data);
    storetree(root->right);
}
void restoretree(node*root, int& i) {
    if (!root) {
        return;
    }
    restoretree(root->left, i);
    root->data = v[i];
    i;
    restoretree(root->right, i);
}
void converttobst(node*root) {
    if (!root) {
        return;
    }
    storetree(root);
    sort(v.begin(), v.end());
    int i = 0;
    restoretree(root, i);
}
int main() {
    node* root = new node(3);
    root->left = new node(1);
    root->right = new node(7);
    root->left->left = new node(4);
    root->left->right = new node(5);
    root->left->left->right = new node(2);
    root->right->left = new node(6);
    root->right->right = new node(9);
    root->right->right->left = new node(8);
    cout << "the inorder traversal of the tree is : "; inorder(root); cout << endl;
    converttobst(root);
    cout << "the inorder traversal of the tree is : "; inorder(root); cout << endl;
}

将二叉树转换为 bst 算法的复杂度

时间复杂度

平均情况

我们将数组存储在 sorted 中，并将 sorted 数组存储回二叉树，进行无序遍历的时间复杂度为 o(n)。但是，对数组进行排序的复杂度是 o(nlogn)，因此总复杂度给定为 o(nlogn) 2*o(n)。时间复杂度为 o(nlogn)。

最佳情况

最佳情况下的时间复杂度为 o(n)。当给定的二叉树已经是一个 bst 时，我们做无序遍历来实现它，而且不需要排序操作。

最坏情况

最坏情况下的时间复杂度为 o(nlogn)。

空间复杂度

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

上一篇：二叉搜索树中序后代

下一篇：没有了

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

本文地址：

发布时间：2023/08/31 浏览次数：176 分类：c

本文将讨论使用 c 中的 delete 关键字为二叉搜索树创建析构函数。c 二叉搜索树析构函数

c 中逐级打印二叉树中的数据

发布时间：2023/08/27 浏览次数：205 分类：c

二叉树的逐层遍历称为广度优先遍历。本教程将教您如何使用 c 逐级打印二叉树中的数据，并让您熟悉执行此任务的不同方法。

发布时间：2023/08/11 浏览次数：64 分类：java

在这篇深入的文章中，我们将在实现递归搜索程序以确定 java 程序中树的高度之前学习二叉搜索树的基础知识。要理解本文，我们建议大家对树的数据结构概念有基本的了解。二叉搜索树

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

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

二叉搜索树检查

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

如何检查给定的二叉树是否是二叉搜索树。

二叉搜索树迭代插入

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

本教程介绍二叉搜索树中的迭代插入。

将二叉树转换为二叉搜索树-ag捕鱼王app官网