Блог

Я в замешательстве, функция binaryTreeToBST , которая выполняет перечисленные ниже операции и вызывает функцию. Почему мы не добавляем временные сложности каждой вызываемой функции вместо того, чтобы учитывать только временную сложность сортировки (шаг 3 ниже)?

1. Количество узлов
2. Создание временного массива arr [], в котором хранится обход дерева по порядку. (берет O(n) )
3. отсортируйте временный массив arr[]. Этот шаг занимает O(nlogn) времени.
4. Снова выполните обход по порядку, чтобы преобразовать BT в BST(требуется O(n) )

 /* A program to convert Binary Tree to Binary Search Tree */
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node structure */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

/* A helper function that stores inorder traversal of a tree rooted
with node */
void storeInorder(struct node* node, int inorder[], int* index_ptr)
{
    // Base Case
    if (node == NULL)
        return;

    /* first store the left subtree */
    storeInorder(node->left, inorder, index_ptr);

    /* Copy the root's data */
    inorder[*index_ptr] = node->data;
    (*index_ptr)  ; // increase index for next entry

    /* finally store the right subtree */
    storeInorder(node->right, inorder, index_ptr);
}

/* A helper function to count nodes in a Binary Tree */
int countNodes(struct node* root)
{
    if (root == NULL)
        return 0;
    return countNodes(root->left)   countNodes(root->right)   1;
}

// Following function is needed for library function qsort()
int compare(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

/* A helper function that copies contents of arr[] to Binary Tree.
This function basically does Inorder traversal of Binary Tree and
one by one copy arr[] elements to Binary Tree nodes */
void arrayToBST(int* arr, struct node* root, int* index_ptr)
{
    // Base Case
    if (root == NULL)
        return;

    /* first update the left subtree */
    arrayToBST(arr, root->left, index_ptr);

    /* Now update root's data and increment index */
    root->data = arr[*index_ptr];
    (*index_ptr)  ;

    /* finally update the right subtree */
    arrayToBST(arr, root->right, index_ptr);
}

// This function converts a given Binary Tree to BST
void binaryTreeToBST(struct node* root)
{
    // base case: tree is empty
    if (root == NULL)
        return;

    /* Count the number of nodes in Binary Tree so that
    we know the size of temporary array to be created */
    int n = countNodes(root);

    // Create a temp array arr[] and store inorder traversal of tree in arr[]
    int* arr = new int[n];
    int i = 0;
    storeInorder(root, arr, amp;i);

    // Sort the array using library function for quick sort
    qsort(arr, n, sizeof(arr[0]), compare);

    // Copy array elements back to Binary Tree
    i = 0;
    arrayToBST(arr, root, amp;i);

    // delete dynamically allocated memory to avoid memory leak
    delete[] arr;
}

/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
    struct node* temp = new struct node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

/* Utility function to print inorder traversal of Binary Tree */
void printInorder(struct node* node)
{
    if (node == NULL)
        return;

    /* first recur on left child */
    printInorder(node->left);

    /* then print the data of node */
    printf("%d ", node->data);

    /* now recur on right child */
    printInorder(node->right);
}

/* Driver function to test above functions */
int main()
{
    struct node* root = NULL;

    /* Constructing tree given in the above figure
        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);

    // convert Binary Tree to BST
    binaryTreeToBST(root);

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

    return 0;
}