Преобразование двоичного дерева в двоичное дерево поиска


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple Bloomberg Google Microsoft VMware
Двоичное дерево поиска Двоичное дерево Поиск в глубину дерево Обход дерева

В задаче преобразования двоичного дерева в двоичное дерево поиска мы дали двоичное дерево преобразовать его в двоичное дерево поиска без изменения структуры дерево.

Пример

вход

Преобразование двоичного дерева в двоичное дерево поиска

Результат

Преобразование двоичного дерева в двоичное дерево поиска

предзаказ: 13 8 6 47 25 51

Алгоритм

Нам не нужно изменять структуру двоичного дерева и преобразовывать его в двоичное дерево поиска. Обратите внимание на свойство двоичного дерева поиска, что порядок пересечение Двоичного дерева поиска приводит к отсортированным данным. Воспользуемся этим свойством для достижения желаемого результата.

Идея состоит в том, чтобы сохранить неупорядоченный обход двоичного дерева в массив, отсортируйте массив, а затем просмотрите массив и двоичное дерево (в неупорядоченном виде) и замените каждый узел в двоичном дереве соответствующим элементом в массиве. Это преобразует двоичное дерево в двоичное дерево поиска.

  1. Создайте массив с именем inOrder.
  2. Просмотрите данное двоичное дерево в упорядоченном виде и сохраните значение узлов в массиве inOrder.
  3. Отсортируйте массив.
  4. Одновременно просмотрите массив и двоичное дерево в упорядоченном виде и замените значение соответствующего узла в двоичном дереве значением в массиве inOrder.
  5. Двоичное дерево преобразуется в двоичное дерево поиска.

Сложность времени = O (n log (n))
Сложность пространства = O (n), поскольку мы использовали массив для хранения обхода по порядку
где n - номер узла в данном двоичном дереве.

объяснение

Рассмотрим двоичное дерево, показанное в примере выше.

Шаг 1 и 2

Сохраните порядок обхода двоичного дерева в массиве.
inOrder [] = {47, 51, 25, 6, 13, 8}

Шаг 3

Отсортируйте массив.
inOrder = {6, 8, 13, 25, 47, 51}

Шаг 4

Одновременно просмотрите массив и двоичное дерево и замените элемент двоичного дерева соответствующим элементом отсортированного массива inOrder.
Двоичное дерево теперь выглядит так:

Двоичное дерево преобразуется в двоичное дерево поиска.

Код JAVA для преобразования двоичного дерева в двоичное дерево поиска

import java.util.ArrayList;
import java.util.Collections;

public class BinaryTreeToBinarySearchTreeConversion {
    // class representing Node of a Binary Tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // class to provide a wrapper around index
    // so that we can pass it by reference
    static class Index {
        int index;

        public Index(int index) {
            this.index = index;
        }
    }

    // function to print pre order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // function to traverse in binary tree in in-order form and store the elements
    // in a list
    private static void inOrderAndFormList(Node root, ArrayList<Integer> inorder) {
        if (root != null) {
            inOrderAndFormList(root.left, inorder);
            // store the current value in the list
            inorder.add(root.data);
            inOrderAndFormList(root.right, inorder);
        }
    }

    // function to traverse in binary tree in in-order form and
    // change the value of elements accordingly
    private static void inOrderAndChange(Node root, ArrayList<Integer> inOrder, Index index) {
        if (root != null) {
            inOrderAndChange(root.left, inOrder, index);
            // change the current element of Tree with current element of list
            root.data = inOrder.get(index.index);
            // increment index by 1
            index.index++;
            inOrderAndChange(root.right, inOrder, index);
        }
    }

    private static void convertToBST(Node root) {
        // create a list and store the inorder of the given Binary Tree
        ArrayList<Integer> inOrder = new ArrayList<>();
        inOrderAndFormList(root, inOrder);

        // Sort the list
        Collections.sort(inOrder);

        // traverse in binary tree and list simultaneously and change the required values
        inOrderAndChange(root, inOrder, new Index(0));
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(25);
        root.left = new Node(51);
        root.right = new Node(13);
        root.left.left = new Node(47);
        root.right.left = new Node(6);
        root.right.right = new Node(8);

        convertToBST(root);

        preOrder(root);
        System.out.println();
    }
}
13 8 6 47 25 51

Код C ++ для преобразования двоичного дерева в двоичное дерево поиска

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// class representing Node of a Binary Tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
    }
};

// global variable index
int index = 0;

void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
void inOrderAndFormList(Node *root, vector<int> &inOrder) {
    if (root != NULL) {
        inOrderAndFormList(root->left, inOrder);
        // store the current value in the list
        inOrder.push_back(root->data);
        inOrderAndFormList(root->right, inOrder);
    }
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
void inOrderAndChange(Node *root, vector<int>& inOrder) {
    if (root != NULL) {
        inOrderAndChange(root->left, inOrder);
        
        // change the current element of Tree with current element of list
        root->data = inOrder[index];
        index++;
        
        inOrderAndChange(root->right, inOrder);
    }
}

void convertToBST(Node *root) {
    // create a list and store the inorder of the given Binary Tree
    vector<int> inOrder;
    inOrderAndFormList(root, inOrder);

    // Sort the list
    sort(inOrder.begin(), inOrder.end());

    // traverse in binary tree and list simultaneously and change the required values
    index = 0;
    inOrderAndChange(root, inOrder);
}

int main() {
    // Example Tree
    Node *root = new Node(25);
    root->left = new Node(51);
    root->right = new Node(13);
    root->left->left = new Node(47);
    root->right->left = new Node(6);
    root->right->right = new Node(8);

    convertToBST(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
13 8 6 47 25 51

дело