使用STL集C ++将二进制树转换为二进制搜索树？

如果是给定的二叉树，则将其转换为二叉搜索树，以保持二叉树的原始结构完整无缺。

此解决方案将使用C ++ STL集，而不是基于数组的解决方案。

例子

例子1

输入值

输出结果

例子2

输入值

      11
     /   \
    31    16
   /        \
 21         6

输出结果

     16
    /   \
  11     21
 /         \
 6          31

解

在执行顺序遍历时，我们必须将二叉树的项目复制到一组中。这消耗O（n log n）时间。请注意，C ++ STL（标准模板库）中的设置是使用自平衡二进制搜索树（如红黑树，AVL树等）实现的。
无需对集合进行排序，因为C ++中的集合用于实现自平衡二进制搜索树，因此插入，搜索，删除等每个操作都消耗O（log n）时间。
现在，我们可以在执行树的有序遍历的同时轻松地从开始到树一一地复制集合的元素。从开始复制集合的每个项目时要小心，我们首先在进行有序遍历的同时将其复制到树中，然后再将其从集合中删除。
当前，上述解决方案比此处说明的将二进制树转换为二进制搜索树的基于数组的转换更容易实现。

下面说明了使用set将二进制树转换为二进制搜索树(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;
};
//用于在执行有序遍历时将节点存储在集合中的功能。
void storeinorderInSet(Node1* root1, set<int>& s){
   if (!root1)
   return;
   //首先访问左子树
   storeinorderInSet(root1->left, s);
   Order of O(logn) for sets is taken by insertion
   s.insert(root1->data);
   //我们访问正确的子树
   storeinorderInSet(root1->right, s);
} // Time complexity = O(nlogn)
//用于在执行顺序遍历时将一组一组的元素复制到树中的功能
void setToBST(set<int>& s, Node1* root1){
   //基本条件
   if (!root1) return;
   //我们首先移至左侧子树并更新元素
   setToBST(s, root1->left);
   //迭代器最初指向set的开始
   auto it = s.begin();
   //我们将在set(sorted)处理时将元素复制到树上。
   root1->data = *it;
   //现在我们从集合中删除起始元素。
   s.erase(it);
   //现在我们移到右边的子树并更新元素
   setToBST(s, root1->right);
}
//T(n)= O(nlogn)时间
//我们将二叉树转换为BST。
void binaryTreeToBST(Node1* root1){
   set<int> s;
   //我们用树的有序遍历数据填充集合
   storeinorderInSet(root1, s);
   //当前，默认情况下按使用顺序对集进行排序
   implementing self-balancing BST
   //我们将元素从集合中复制到树上，同时进行有序遍历
   which makes a BST
   setToBST(s, root1);
}
//时间复杂度= O(nlogn)，
//辅助空间= O(n)。
//用于创建节点的辅助功能
Node1* newNode(int data){
   //动态分配内存
   Node1* temp = new Node1();
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
//进行顺序遍历的功能
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 */
   //我们将上面的二叉树转换为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)

基础教程