3

ソートされた配列を使用して、バランスのとれた二分探索木を構築する予定です。プログラムが終了するまで、すべてがうまくいきました。二分探索木のデストラクタに問題があるようです。

エラー情報:

プログラムは信号 EXC_BAD_ACCESS を受信しました。メモリにアクセスできませんでした。理由: KERN_PROTECTION_FAILURE のアドレス: 0x00007fff5f3ffff8 0x0000000100002857 in BST_Node::~BST_Node (this=0x100100920) at BST_Node.h:18 ~BST_Node() {delete parent; 左を削除します。権利を削除;}

#ifndef BST_NODE_H
#define BST_NODE_H

#include <cstddef>

class BST_Node {
    public:
        BST_Node(int k) : key(k), parent(NULL), left(NULL), right(NULL) {}
        ~BST_Node() {if (parent!=NULL) delete parent;if (left!=NULL) delete left;if (right!=NULL) delete right;}
        // data member
        int key;
        BST_Node* parent;
        BST_Node* left;
        BST_Node* right;
};

#endif

#include <iostream>
#include <vector>
#include "BST_Tree.h"
#include "BST_Node.h"

using namespace std;

// use recursion to construct the tree. Find the mid of the array to be the root of the subtree. Use left part of the array to construct the left subtree and right part to construct the right subtree.
BST_Node* CreateTree(vector<int> &a, int start, int end) {
    if (end<start) {
        return NULL;
    } else {
        int mid = (start+end+1)/2;
        BST_Node* p = new BST_Node(a[mid]);
        BST_Node* l_tmp = CreateTree(a, start, mid-1);
        if (l_tmp)
            l_tmp->parent = p;
        p->left = l_tmp;
        BST_Node* r_tmp = CreateTree(a, mid+1, end);
        if (r_tmp)
            r_tmp->parent = p;
        p->right = r_tmp;
        return p;
    }
}

int main() {
    vector<int> a;
    a.push_back(0);
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);
    a.push_back(6);
    BST_Tree t;
    t.root = CreateTree(a, 0, 6);
    t.InOrderWalk(t.root);
    return 0;
}

どうもありがとうございました！

4

2 に答える 2

2

所有関係 (オブジェクトが不要になったときに別のオブジェクトを削除する責任がある場合) には、循環があってはなりません。あなたの場合、子を所有する親ノードがあり、その逆もあります。

ルート ノードが削除されると、そのコンストラクターは最初に左側の子を削除します。子のデストラクタは、すでに削除されている親を削除します。

ツリーの典型的な所有関係は、親ノードが子を所有するというものです。子には、所有権を持たない親へのポインターがあります。子ノードは親ノードの破棄の一部として削除されるため、そのポインターは子ノードの存続期間中有効なままになります。

したがって、デストラクタは次のようにする必要があります。

BST_Node::~BST_Node() {
   delete left;
   delete right;
}

その他の注意事項：

  • NULL ポインターをチェックする必要はありません。null ポインターを削除しても安全であり、何もしません。
  • BST_Node オブジェクトのコピーを防止する必要があります。暗黙的に定義されたコピー コンストラクターとコピー代入演算子は、同じ子ノードを所有する別のオブジェクトを作成し、オブジェクトが二重に削除されます。

ポインターの所有権セマンティクスを表現する最善の方法は、適切なスマート ポインター クラスを使用することです。あなたの場合、最も適切な宣言は

class BST_Node {
    public:
        ~BST_Node() = default; // you can simply omit this completely

        // other things

        BST_Node* parent; // no ownership
        std::unique_ptr<BST_Node> left;  // exclusive ownership
        std::unique_ptr<BST_Node> right;
};

これの便利な追加効果として、暗黙的に生成されたコピー操作は抑制されますstd::unique_ptr<T>。

于 2013-02-02T18:48:08.573 に答える