数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 STL set 在 C++ 中将二叉树转换为二叉搜索树？
对于给定的二叉树，将其转换为二叉搜索树，同时保持二叉树的原始结构不变。
此解决方案将使用 C++ STL 的集合，而不是基于数组的解决方案。
示例
示例 1
输入
11 / \ 3 8 / \ 9 5
输出
9 / \ 5 11 / \ 3 8
示例 2
输入
11 / \ 31 16 / \ 21 6
输出
16 / \ 11 21 / \ 6 31
解决方案
我们必须在执行中序遍历的同时将二叉树的元素复制到一个集合中。这需要 O(n log n) 的时间。请注意，C++ STL（标准模板库）中的集合是使用自平衡二叉搜索树实现的，例如红黑树、AVL 树等。
无需对集合进行排序，因为 C++ 中的集合是使用自平衡二叉搜索树实现的，因此每个操作（如插入、搜索、删除等）都需要 O(log n) 的时间。
现在，我们可以轻松地从集合的开头开始，将集合中的元素逐一复制到树中，同时执行树的中序遍历。需要注意的是，当从集合的开头复制每个元素时，我们首先在执行中序遍历的同时将其复制到树中，然后将其从集合中删除。
目前，上述解决方案比这里解释的基于数组的将二叉树转换为二叉搜索树的转换更简单易于实现。
以下程序说明了如何使用集合将二叉树转换为二叉搜索树 (BST)。
示例
/* CPP program for converting a Binary tree to BST implementing sets as containers. */
#include <bits/stdc++.h>
using namespace std;
struct Node1 {
int data;
struct Node1 *left, *right;
};
// function for storing the nodes in set while performing inorder traversal.
void storeinorderInSet(Node1* root1, set<int>& s){
if (!root1)
return;
// Left subtree is visited first
storeinorderInSet(root1->left, s);
Order of O(logn) for sets is taken by insertion
s.insert(root1->data);
// We visit the right subtree
storeinorderInSet(root1->right, s);
} // Time complexity = O(nlogn)
// function for copying elements of set one by one to the tree while performing inorder traversal
void setToBST(set<int>& s, Node1* root1){
// base condition
if (!root1) return;
// We first move to the left subtree and update elements
setToBST(s, root1->left);
// iterator initially pointing to the starting of set
auto it = s.begin();
// We copy the element at sarting of set(sorted) to the tree.
root1->data = *it;
// now we erase the starting element from set.
s.erase(it);
// now we move to right subtree and update elements
setToBST(s, root1->right);
}
// T(n) = O(nlogn) time
// We convert Binary tree to BST.
void binaryTreeToBST(Node1* root1){
set<int> s;
// We populate the set with the tree's inorder traversal data
storeinorderInSet(root1, s);
// At present sets are by default sorted as they are used
implementing self-balancing BST
// We copy elements from set to the tree while inorder traversal
which makes a BST
setToBST(s, root1);
}
// Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function for creating a node
Node1* newNode(int data){
// dynamically allocating memory
Node1* temp = new Node1();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// function for doing inorder traversal
void inorder(Node1* root1){
if (!root1)
return;
inorder(root1->left);
cout<< root1->data << " ";
inorder(root1->right);
}
int main(){
Node1* root1 = newNode(6);
root1->left = newNode(8);
root1->right = newNode(10);
root1->right->left = newNode(11);
root1->left->left = newNode(2);
root1->left->right = newNode(7);
root1->right->right = newNode(12);
/* Building tree given in the following figure
6
/ \
8 10
/\ / \
2 7 11 12 */
// We convert the above Binary tree to BST
binaryTreeToBST(root1);
cout<< "Inorder traversal of BST is: " << endl;
inorder(root1);
return 0;
}输出
Inorder traversal of BST is: 1 5 6 7 9 10 11
时间复杂度表示为：O(n Log n)
辅助空间表示为：(n)
更新于： 2020 年 1 月 29 日
586 次浏览
广告