c++ - 基本数组格式的二叉搜索树

Question

我正在尝试将一堆整数读入一个数组，然后使用一个函数将该数组逐个元素作为输入元素并创建一个二叉搜索树。 bst 是数组的形式，在 (2n+1) 数组点有较小的元素，在 2n+2 数组点有较大的元素。我认为我的大部分工作正常，但出于某种原因，我的函数中的循环无法正常工作。有什么解决办法吗？？我想我只是没有看到什么。

代码::

#include <iostream>
#include <fstream>
using namespace std;


void sortArray(int arr[], int size)
{   
    int bst[50];
    bst[0] = arr[0];

    for(int b = 1; b < size - 1; b++)
    {
        int c = 0;
        do{
            if(arr[b] < bst[c])
                {
                    c = ((2 * c) + 1);
                }
            if(arr[b] > bst[c])
                {
                    c = ((2 * c) + 2);
                }
        }while(bst[c] != 0);
        bst[c] = arr[b];
    }

    for(int p = 0; p < 25; p++){
        cout << bst[p];
    }   
}    



int main(int argc, char** argv) {
int myArray[50];
int i = 0;

ifstream myfile ("tree_nodes.txt");
if (myfile.is_open())
{
    while (! myfile.eof() )
    {
        myfile >> myArray[i];
        i++;
    }
    myfile.close();
}
else cout << "Unable to open file";

for(int p = 0; p < (i); p++){
        cout << myArray[p];
    }

sortArray(myArray,i);


return 0;
}

Answer 1

您的代码存在不少问题。

1. 您正在创建一个不平衡的 BST，可能需要 2^N 空间来存储树。即要“排序”32 个元素，您可能需要 4GB 的内存。您的 50 元素数组只能可靠地对 4 个整数进行排序。
2. 您依赖整数 0 来表示“无值”。 0 不能是初始数据的一部分。
3. int bst[50] 未初始化。内容未知，不为零。 int bst[50] = {};，参见例如http://www.cplusplus.com/doc/tutorial/arrays/
4. 您的方法无法处理两个具有相同值的整数。
5. 我的印象是您希望最后一个 for 语句输出排序的整数。事实并非如此。

简而言之:这种方法行不通。创建 BST 很棘手。我建议您研究一个已经存在的平衡 BST 实现。

要解决 5. 你可以使用类似的东西:

void visitAndPrintOddBST(int bst[], int index = 0){
    if (bst[index] == 0 ) return;
    visitAndPrintOddBST(bst, index*2 + 1);
    std::cout << bst[index] << std::endl;
    visitAndPrintOddBST(bst, index*2 + 2);
}

您需要某种堆栈来跟踪树中的移动。在这种方法中，这是递归调用堆栈。数组的大小也是未指定的，很可能会超出范围。这不是好的代码。 仅用于此实验。