0

我的程序很简单，做一个树（min heap），并通过一个中序遍历将数据存储到一个数组中，然后销毁树（heap）。

当我运行到存储步骤时，程序崩溃了。即使我知道错误位置，我也找不到原因（我注释了一些代码并运行以查看它是否有效，最后我找到了错误位置）

我想也许我删除了一个无效的指针，但我找不到在哪里；请帮我找到它。

当我输入

6
1 2 3 4 5 6

当我输入时它工作

8
90 80 30 40 10 45 20 50

然后崩溃。

我不知道这两个组号有什么不同

#include <iostream>

typedef int ElementType;

struct BTree
{
    ElementType data;
    BTree *Left;
    BTree *Right;
};

class BuildingMinHeap
{
    ElementType *Elements;
    int Size;
    int Capacity;
    BTree *root;
    ElementType *inorder_array; // to store members inorderly

public:
    BuildingMinHeap(int MaxSize, ElementType MinData): Size(0), Capacity(MaxSize+1)
    {
        Elements = new ElementType[MaxSize+1];
        Elements[0] = MinData;  // sentinel
        root = NULL;
        inorder_array = new ElementType[Size];  
    }

    ~BuildingMinHeap()
    {
       if (Elements)
           delete [] Elements;
       if (inorder_array)
           delete [] inorder_array;
       if (root != NULL)
           DeleteBTree(root);
    }

    void Insert(ElementType item);

    void genBTree(ElementType *a, int position);    // call CreateBTree()

    void ModifyArray(ElementType *input, int size); // call gen_inorder_array()


    ElementType *getElements()  {return Elements;}
    BTree *getRoot()    {return root;}
    void DeleteBTree(BTree *root);


private:
    BTree *CreateBTree(ElementType *a, int position);
    void gen_inorder_array(const BTree *node);
};

void BuildingMinHeap::Insert(ElementType item)
{
    int i;

    i = ++Size;
    for (; Elements[i/2] > item; i /= 2)
    {
        // Elements[0] is sentinel
        Elements[i] = Elements[i/2];
    }
    Elements[i] = item;
}

BTree *BuildingMinHeap::CreateBTree(ElementType *a, int position)   // array to Binary Tree list
{
    BTree *new_node = new BTree;
    if (position > Size)
        return NULL;

    new_node->data = a[position];
    new_node->Left = CreateBTree(a, 2*position);
    new_node->Right = CreateBTree(a, 2*position+1);

    return new_node;

}

void BuildingMinHeap::genBTree(ElementType *a, int position)    // call CreateBTree()
{
    root = CreateBTree(a, position);
}

void BuildingMinHeap::DeleteBTree(BTree *root)
{
    if (root == NULL)
        return;
    DeleteBTree(root->Left);
    DeleteBTree(root->Right);
    delete root;
    root = NULL;
    return;
}

void BuildingMinHeap::gen_inorder_array(const BTree *node)   // to generate members of tree root inorderly
{
    static int index = 0;
    // like print inorder tree
    if (node)
    {
        gen_inorder_array(node->Left);
        inorder_array[index++] = node->data;
//        std::cout << node->data << " ";
        gen_inorder_array(node->Right);
    }
}


void BuildingMinHeap::ModifyArray(int *input, int size) // call gen_inorder_array()
{

    gen_inorder_array(root); // generate inorder_array, when I comment this line, it work
    // below commented code is nothing about tree root member

//
//    // generate<elements of inorder_array,elements' address of Elements> map
//    std::map<int, int*> inorder_Ele_map;
//    for (int i = 0; i != Size; i++)
//    {
//        ElementType *it = std::find(Elements+1, Elements+Size, *(inorder_array+i));
//        inorder_Ele_map[*(inorder_array+i)] = Elements + (it-Elements);
//    }
//    
//
//    // change Elements array according input array
//    for (int i = 0; i != size; i++)
//    {
//        if (*(inorder_array+i) != *(input+i))
//        {
//            *(inorder_Ele_map[*(inorder_array+i)]) = *(input+i);
//        }
//    }
}




int main(void)
{
    int n;
    std::cin >> n;
    int *input = new int[n];
    for (int i = 0; i != n; i++)
        std::cin >> input[i];

    BuildingMinHeap h(n, -999); // empty heap;
    for (int i = 0; i != n; i++)
        h.Insert(input[i]); // insert element to heap

    h.genBTree(h.getElements(), 1); // generate Binary Tree(pointer) from Elements array, index 1 begin
    // so far it work
    h.ModifyArray(input, n);    // if I comment this line, it would work
    h.DeleteBTree(h.getRoot()); // I have already do call this function in destructor, 
                                // but in destructor I call it when root != NULL, 
                                // I have no idea when I comment this line, there are a crash.

    delete [] input;

    return 0;
}
4

0 回答 0