Рубрики

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

Если дано Двоичное дерево, конвертируйте его в Двоичное дерево поиска. Преобразование должно быть сделано таким образом, чтобы сохранить исходную структуру двоичного дерева.

Примеры.

Example 1
Input:
          10
         /  \
        2    7
       / \
      8   4
Output:
          8
         /  \
        4    10
       / \
      2   7


Example 2
Input:
          10
         /  \
        30   15
       /      \
      20       5
Output:
          15
         /  \
       10    20
       /      \
      5        30

Решение
Ниже приводится трехэтапное решение для преобразования двоичного дерева в двоичное дерево поиска.
1) Создайте временный массив arr [], в котором будет храниться обход дерева. Этот шаг занимает O (N) времени.
2) Сортировать временный массив arr []. Временная сложность этого шага зависит от алгоритма сортировки. В следующей реализации используется быстрая сортировка, которая занимает (n ^ 2) времени. Это можно сделать за O (nLogn), используя сортировку кучи или сортировку слиянием.
3) Снова выполните обход по порядку дерева и скопируйте элементы массива в узлы дерева один за другим. Этот шаг занимает O (N) времени.

Ниже приводится реализация вышеуказанного подхода. Основная функция для преобразования выделена в следующем коде.

С

/ * Программа для преобразования двоичного дерева в двоичное дерево поиска * /
#include<stdio.h>
#include<stdlib.h>

  
/ * Бинарная древовидная структура * /

struct node

{

    int data;

    struct node *left;

    struct node *right;

};

  
/ * Вспомогательная функция, которая хранит обход по порядку дерева с корнем

  с узлом * /

void storeInorder (struct node* node, int inorder[], int *index_ptr)

{

    // Базовый вариант

    if (node == NULL)

        return;

  

    / * сначала сохранить левое поддерево * /

    storeInorder (node->left, inorder, index_ptr);

  

    / * Копировать данные рута * /

    inorder[*index_ptr] = node->data;

    (*index_ptr)++;  // увеличиваем индекс для следующей записи

  

    / * наконец сохранить правильное поддерево * /

    storeInorder (node->right, inorder, index_ptr);

}

  
/ * Вспомогательная функция для подсчета узлов в двоичном дереве * /

int countNodes (struct node* root)

{

    if (root == NULL)

     return 0;

    return countNodes (root->left) +

           countNodes (root->right) + 1;

}

  
// Следующая функция необходима для библиотечной функции qsort ()

int compare (const void * a, const void * b)

{

    return ( *(int*)a - *(int*)b );

}

  
/ * Вспомогательная функция, которая копирует содержимое arr [] в Binary Tree.

   Эта функция в основном выполняет обход Inorder для Binary Tree и

   один за другим копировать элементы arr [] в узлы двоичного дерева * /

void arrayToBST (int *arr, struct node* root, int *index_ptr)

{

    // Базовый вариант

    if (root == NULL)

      return;

  

    / * сначала обновить левое поддерево * /

    arrayToBST (arr, root->left, index_ptr);

  

    / * Теперь обновите данные root и индекс приращения * /

    root->data = arr[*index_ptr];

    (*index_ptr)++;

  

    / * наконец обновить правильное поддерево * /

    arrayToBST (arr, root->right, index_ptr);

}

  
// Эта функция преобразует данное двоичное дерево в BST

void binaryTreeToBST (struct node *root)

{

    // базовый случай: дерево пусто

    if(root == NULL)

       return;

  

    / * Подсчитать количество узлов в двоичном дереве так, чтобы

       мы знаем размер создаваемого временного массива * /

    int n = countNodes (root);

  

    // Создание временного массива arr [] и сохранение обхода дерева по порядку в arr []

    int *arr = new int[n];

    int i = 0;

    storeInorder (root, arr, &i);

  

    // Сортируем массив, используя библиотечную функцию для быстрой сортировки

    qsort (arr, n, sizeof(arr[0]), compare);

  

    // Копируем элементы массива обратно в двоичное дерево

    i = 0;

    arrayToBST (arr, root, &i);

  

    // удаляем динамически выделенную память, чтобы избежать утечки памяти

    delete [] arr;

}

  
/ * Служебная функция для создания нового узла двоичного дерева * /

struct node* newNode (int data)

{

    struct node *temp = new struct node;

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;

}

  
/ * Утилита для печати обхода по порядку двоичного дерева * /

void printInorder (struct node* node)

{

    if (node == NULL)

        return;

  

    / * первый рецидив на левом ребенке * /

    printInorder (node->left);

  

    / * затем распечатать данные узла * /

    printf("%d ", node->data);

  

    / * теперь возвращаемся на правильного ребенка * /

    printInorder (node->right);

}

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

    struct node *root = NULL;

  

    / * Построение дерева приведено на рисунке выше

          10

         / /

        30 15

       / /

      20 5 * /

    root = newNode(10);

    root->left = newNode(30);

    root->right = newNode(15);

    root->left->left = newNode(20);

    root->right->right = newNode(5);

  

    // преобразовать двоичное дерево в BST

    binaryTreeToBST (root);

  

    printf("Following is Inorder Traversal of the converted BST: \n");

    printInorder (root);

  

    return 0;

}

питон

# Программа для преобразования двоичного дерева в BST

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data  = data 

        self.left = None

        self.right = None

  
# Вспомогательная функция для хранения обхода дерева inroder

def storeInorder(root, inorder):

      

    # Базовый вариант

    if root is None:

        return 

      

    # Сначала сохраните левое поддерево

    storeInorder(root.left, inorder)

      

    # Копировать данные рута

    inorder.append(root.data)

  

    # Наконец, сохраните правильное поддерево

    storeInorder(root.right, inorder)

  
# Вспомогательная функция для подсчета узлов в двоичном дереве

def countNodes(root):

    if root is None:

        return 0

  

    return countNodes(root.left) + countNodes(root.right) + 1

  
# Вспомогательная функция, которая копирует содержимое отсортированного массива
# к бинарному дереву

def arrayToBST(arr, root):

  

    # Базовый вариант

    if root is None:

        return 

      

    # Сначала обновите левое поддерево

    arrayToBST(arr, root.left)

  

    # теперь обновляем данные root удаляем значение из массива

    root.data = arr[0]

    arr.pop(0)

  

    # Наконец обновите правильное поддерево

    arrayToBST(arr, root.right)

  
# Эта функция преобразует данное двоичное дерево в BST

def binaryTreeToBST(root):

      

    # Базовый случай: дерево пусто

    if root is None:

        return 

      

    # Подсчитать количество узлов в двоичном дереве так, чтобы

    # мы знаем размер создаваемого временного массива

    n = countNodes(root)

  

    # Создайте временный массив и сохраните командировку

    № дерева

    arr = []

    storeInorder(root, arr)

      

    # Сортировать массив

    arr.sort()

  

    # копировать элементы массива обратно в двоичное дерево

    arrayToBST(arr, root)

  
# Распечатать обход дерева по порядку

def printInorder(root):

    if root is None:

        return

    printInorder(root.left)

    print root.data, 

    printInorder(root.right)

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(10)

root.left = Node(30)

root.right = Node(15)

root.left.left = Node(20)

root.right.right= Node(5)

  
# Конвертировать двоичное дерево в BST
binaryTreeToBST(root)

  

print "Following is the inorder traversal of the converted BST"

printInorder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)


Выход:

Following is Inorder Traversal of the converted BST:
5 10 15 20 30

Мы рассмотрим другой метод для этой задачи, который преобразует дерево, используя O (высоту дерева) дополнительного пространства.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes