使用STL集将二叉树转换为二叉搜索树


难度级别 中等
经常问 亚马逊 Coursera 谷歌 的确 微软 OYO房间
二进制搜索树 二叉树

问题陈述

我们得到一个 二叉树 我们需要将其转换为 二叉搜索树。 问题“使用STL集进行从二叉树到二进制搜索树的转换”要求使用STL集进行转换。 我们已经讨论过 将二叉树转换为BST 但是我们没有讨论使用Set的转换。 转换时,需要检查的一件事是原始树结构必须保持不变。

使用案列

输入

输出

使用STL集将二叉树转换为二叉搜索树

 

使用Set将二叉树转换为BST的方法

我们已经讨论过将二叉树转换为二叉树的方法,但是这里我们将使用内置的STL集。 因此,方法之一可能是首先构造一个平衡的二叉搜索树,即 AVL树或红黑 树。 然后,我们对新创建的树进行有序遍历,并以类似的有序方式将内容复制回原始树。

上面讨论的方法需要创建不必要的自平衡二叉树。 因此,为避免这种情况,我们讨论了一种基于阵列的方法。 在这种方法中,我们首先进行了 遍历 三个中的一个,然后对数组进行排序。 再次使用顺序遍历,我们替换了初始树中的元素。

在这种方法中,我们将不会创建数组然后对其进行排序。 我们将使用使元素保持排序方式的集合。 因此,我们将遍历树并继续将元素插入到 。 之后,我们将替换给定树中的元素。

代码

C ++代码使用Set将二进制树转换为BST

#include <bits/stdc++.h>
using namespace std;

// defines the structure of a tree node
struct node{
    int data;
    node* left;
    node* right;
};

// inserts the given tree elements into the set
void insertIntoSet(node* root, set<int> &treeSet){
    if(root){
        insertIntoSet(root->left, treeSet);
        treeSet.insert(root->data);
        insertIntoSet(root->right, treeSet);
    }
}

// replace the elements of the initial tree
// with elements in treeSet in in-order fashion
void modifyBinaryTreeIntoBST(node* root, set<int> &treeSet)
{
    if(root){
        modifyBinaryTreeIntoBST(root->left, treeSet);
        root->data = *(treeSet.begin());
        treeSet.erase(treeSet.begin());
        modifyBinaryTreeIntoBST(root->right, treeSet);
    }
}

// Converts Binary tree to BST
void binaryTreeToBST(node* root)
{
    set<int> treeSet;
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
}

// creates and returns a new node with supplied node value
node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

// simple in-order traversal
void inorder(node *root){
    if(root){
        inorder(root->left);
        cout<<root->data;
        inorder(root->right);
    }
}

int main()
{
    // constructing a binary tree
    // same as shown above
    node *root = create(1);
    root->right = create(2);
    root->right->left = create(4);
    root->right->left->left = create(5);
    root->right->left->right = create(3);

    cout<<"Inorder Traversal of given binary tree"<<endl;
    inorder(root);cout<<endl;
    binaryTreeToBST(root);
    cout<<"Inorder Traversal of modified tree\n";
    inorder(root);
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

Java代码使用Set将二进制树转换为BST

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  // creates and returns a new node with supplied node value
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  // inserts the given tree elements into the set
  static void insertIntoSet(node root, TreeSet<Integer> treeSet){
    if(root != null){
      insertIntoSet(root.left, treeSet);
      treeSet.add(root.data);
      insertIntoSet(root.right, treeSet);
    }
  }

  // replace the elements of the initial tree
  // with elements in treeSet in in-order fashion
  static void modifyBinaryTreeIntoBST(node root, TreeSet<Integer> treeSet)
  {
    if(root != null){
      modifyBinaryTreeIntoBST(root.left, treeSet);
      root.data = treeSet.pollFirst();
      modifyBinaryTreeIntoBST(root.right, treeSet);
    }
  }

  // Converts Binary tree to BST
  static void binaryTreeToBST(node root)
  {
    TreeSet<Integer> treeSet = new TreeSet<>();
    // first fill the set
    insertIntoSet(root, treeSet);
    // then replace the elements in initial tree
    modifyBinaryTreeIntoBST(root, treeSet);
  }

  // simple in-order traversal
  static void inorder(node root){
    if(root != null){
      inorder(root.left);
      System.out.print(root.data);
      inorder(root.right);
    }
  }

  public static void main(String[] args)
  {
    // constructing a binary tree
    // same as shown above
    node root = create(1);
    root.right = create(2);
    root.right.left = create(4);
    root.right.left.left = create(5);
    root.right.left.right = create(3);

    System.out.println("Inorder Traversal of given binary tree");
    inorder(root);
    System.out.println();
    binaryTreeToBST(root);
    System.out.println("Inorder Traversal of modified tree");
    inorder(root);
  }
}
Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345

复杂度分析

时间复杂度

O(N log N),  其中N是树中元素的数量。 在这里,对数因子是由于集合而产生的。 设置数据结构需要N倍的时间才能插入,搜索和删除元素。

空间复杂度

上),这里我们已经使用了额外的空间来存储集合中的节点。 因此,转换算法本身具有线性空间复杂度,并且程序整体上也具有线性空间复杂度。