Сортировка массива с использованием бинарного дерева поиска в C ++

Question

Я пытаюсь написать программу, которая сортирует целочисленные элементы массива, используя двоичное дерево поиска (BST) в качестве вспомогательной структуры данных. Идея состоит в том, что после того, как массив задан, можно использовать BST для сортировки его элемента; например:

если мой массив: {120, 30, 115, 40, 50, 100, 70}

, тогда я создаю BST следующим образом:

Как только у меня будет этот BST, я могу выполнить обход дерева порядка, чтобы коснуться каждого узла по порядку, от самого низкого до самого высокого элемента и изменить массив. Результатом будет отсортированный массив {30, 40, 50, 70, 100, 115, 120}

Я написал этот код, и я не понимаю, где я сделал ошибку. Он компилируется без ошибок, но очевидно, что с ним что-то не так:

#include<iostream>
using namespace std;

struct Node
{
    int label;
    Node* left;
    Node* right;
};


void insertSearchNode(Node* &tree, int x)       //insert integer x into the BST
{
    if(!tree){
        tree = new Node;
        tree->label = x;
        tree->right = NULL;
        tree->left = NULL;
        return;
    }
    if(x < tree->label) insertSearchNode(tree->left, x);
    if(x > tree->label) insertSearchNode(tree->right, x);
    return;
}

void insertArrayTree(int arr[], int n, Node* &tree)     //insert the array integer into the nodes label of BST
{
    for(int i=0; i<n; i++){
        insertSearchNode(tree, arr[i]);
    }
    return;
}

int insertIntoArray(int arr[], Node* &tree, int i)      //insert into the array the node label touched during an inorder tree traversal
{
    i=0;
    if(!tree) return 0;
    i += insertIntoArray(arr, tree->left, i) +1;
    arr[i] = tree->label;
    i += insertIntoArray(arr, tree->right, i) +1;
    return i;

}

int main()
{
    Node* maintree;
    maintree = NULL;
    int num;
    cin>>num;
    int arr[num];
    for(int i=0; i<num; i++){    //initialize array with num-elements
     cin>>arr[i];
    }
    insertArrayTree(arr, num, maintree);    //insert elements into BST
    int index;
    insertIntoArray(arr, maintree, index);  //modify array sorting his elements using the BST

    for(int y=0; y<num; y++) cout<< arr[y] << ' ';

    return 0;
}

Я надеюсь, что мой вопрос достаточно ясен. Буду признателен за любую помощь / совет!

Спасибо:)

Answer 1

Единственное, что кажется неправильным - это insertIntoArray().

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

int index;
insertIntoArray(arr, maintree, index);

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

insertIntoArray(arr, maintree, 0);

Я не мог полностью расшифровать вашу версию insertIntoArray(). Но эта версия, кажется, работает.

int insertIntoArray(int arr[], Node* tree, int i)
{
    // If you fall of a leaf then there is nothing to do.
    // So simply return the index as it has not changed.
    if (!tree) {
        return i;
    }


    // Since it is a BST we always go left first.
    // The return value is where we have reached when we
    // have inserted all the left values. 
    i = insertIntoArray(arr, tree->left, i);

    // Now put the current value in and increment the index position.
    arr[i] = tree->label;
    ++i;

    // Now do the right sub-tree.
    i = insertIntoArray(arr, tree->right, i);

    // Return the point index we have reached so far.
    return i;
}

ОК. Так и должно работать. НО это не значит, что это все хороший код C ++. Вы действительно должны проверить этот код.

Answer 2

Так что я немного изменил код. Первое, что нужно заметить, я использую Node** вместо Node* &. Это довольно распространенная идиома при работе с деревьями и алгоритмами обхода. Причина в том, что вы должны иметь возможность изменять передаваемый указатель (я так понимаю, именно поэтому вы использовали Node* &, вы также можете сделать это таким образом). Большая разница с insertIntoArray состоит в том, что int i становится int* i, таким образом, каждый вызов insertIntoArray может использовать один и тот же инкрементный индекс. Я также добавил немного управления памятью.

Я также должен предупредить вас, что int arr[num]; является массивом переменной длины (VLA) и не является стандартным C ++. std::vector - это способ, которым вы должны go. (на самом деле это облегчает эту проблему, потому что вы можете легко добавить)

#include <iostream>

using namespace std;

struct Node
{
    int label;
    Node* left;
    Node* right;

    ~Node() {
      delete left;
      delete right;
    }
};

void insertSearchNode(Node** tree, int x)       //insert integer x into the BST
{
    if (*tree) {
        if (x < (*tree)->label)
            insertSearchNode(&(*tree)->left, x);
        else
            insertSearchNode(&(*tree)->right, x);
    } else {
        *tree = new Node;
        (*tree)->label = x;
        (*tree)->right = NULL;
        (*tree)->left = NULL;
    }
}

void insertArrayTree(int arr[], int n, Node** tree)     //insert the array integer into the nodes label of BST
{
    for (int i = 0; i < n; i++)
        insertSearchNode(tree, arr[i]);
}

void insertIntoArray(int arr[], Node** tree, int* i)      //insert into the array the node label touched during an inorder tree traversal
{
    if (*tree) {
        if ((*tree)->left) insertIntoArray(arr, &(*tree)->left, i);
        arr[(*i)++] = (*tree)->label;
        if ((*tree)->right) insertIntoArray(arr, &(*tree)->right, i);
    }
}

int main()
{
    Node* maintree = NULL;

    int num;
    cin >> num;

    int arr[num];

    for (int i = 0; i < num; i++)    //initialize array with num-elements
        cin >> arr[i];

    insertArrayTree(arr, num, &maintree);    //insert elements into BST
    int index = 0;
    insertIntoArray(arr, &maintree, &index);  //modify array sorting his elements using the BST

    delete maintree;

    for (int y = 0; y < num; y++) 
        cout << arr[y] << ' ';
    cout << '\n';
}