Преобразуване на двоично дърво в двоично дърво за търсене чрез използване на STL набор


Ниво на трудност M
Често задавани в Амазонка Coursera Google Наистина Microsoft OYO Стаи
Двоично дърво за търсене Двоично дърво Дърво

Декларация за проблема

Дадено ни е двоично дърво и трябва да го преобразуваме в бинарно дърво за търсене. Проблемът „Преобразуване на двоично дърво в двоично дърво за търсене чрез използване на набор STL“ изисква да се извърши преобразуване с използване на набор STL. Вече обсъдихме преобразуване на двоичното дърво в BST но не бяхме обсъждали преобразуването с помощта на Set. Докато преобразуването едно нещо, което трябва да се провери, е, че оригиналната дървовидна структура трябва да остане същата.

Пример

Вход

Продукция

Преобразуване на двоично дърво в двоично дърво за търсене чрез използване на STL набор

 

Подход за конвертиране на двоично дърво в BST с помощта на Set

Вече обсъдихме преобразуването на двоично дърво в двоично дърво за търсене, но тук ще използваме вграден STL набор. Така че един от начините може да бъде първо да се изгради балансирано двоично дърво за търсене, което е AVL дърво или червено-черно дърво. И тогава правим вътрешно обхождане на новосъздаденото дърво и копираме съдържанието обратно в оригиналното дърво по подобен начин.

Обсъденият по-горе подход изисква създаването на ненужно самобалансиращо се двоично дърво. Затова, за да избегнем това, обсъдихме подход, основан на масив. При този подход първо направихме a обръщане от трите и след това сортира масива. Отново с вътрешно обръщане заменихме елементите в първоначалното дърво.

При този подход няма да създадем масив и след това да го сортираме. Ще използваме набор, който поддържа елемента в сортиран вид. По този начин ще прекосим дървото и ще продължим да вмъкваме елемента в определен. След това ще заменим елементите в даденото дърво.

код

C ++ код за конвертиране на двоично дърво в BST с помощта на Set

#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 код за конвертиране на двоично дърво в BST с помощта на Set

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 време за вмъкване, търсене и изтриване на елемент.

Сложност на пространството

НА), тук използвахме допълнително пространство за съхраняване на възлите в набора. По този начин алгоритъмът за преобразуване има линейна пространствена сложност, а програмата като цяло също има линейна пространствена сложност.