Перетворення бінарного дерева в бінарне дерево пошуку


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

У проблемі перетворення бінарного дерева в бінарне дерево пошуку ми дали бінарне дерево перетворити його у бінарне дерево пошуку, не змінюючи структури дерево.

Приклад

вхід

Перетворення бінарного дерева в бінарне дерево пошуку

Вихід

Перетворення бінарного дерева в бінарне дерево пошуку

попереднє замовлення: 13 8 6 47 25 51

Алгоритм

Нам не потрібно змінювати структуру бінарного дерева та перетворювати його у бінарне дерево пошуку. Зверніть увагу на властивість бінарного дерева пошуку, яке є inorder обхід бінарного дерева пошуку веде до відсортованих даних. Ми використаємо цю властивість для досягнення бажаного результату.

Ідея полягає в тому, щоб зберегти вхідне обертання двійкового дерева у масив, сортуємо масив, а потім обходимо масив і двійкове дерево (у формі inorder) і замінюємо кожен вузол у двійковому дереві відповідним елементом у масиві. Це перетворить двійкове дерево на двійкове дерево пошуку.

  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

Код С ++ для перетворення бінарного дерева у бінарне дерево пошуку

#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

посилання