1

二分探索木に挿入しようとすると、プログラムでセグメンテーション違反が発生します。ノードの宣言は次のとおりです。

template < class T > class binTreeNode {
friend class binTree < T >;
friend class binSTree < T >;
public:
    // default constructor
    binTreeNode ( const T& newData =T( ), binTreeNode < T >* newLeft = 0, binTreeNode < T >* newRight = 0 ) {
        data = newData;
        left = newLeft;
        right = newRight;
    }
private:
    T data; // data value in node
    binTreeNode < T > *left, *right; // links to other nodes
};

以下の関数はすべて新しいもので、他のすべて (高さ関数やコンストラクターなど) はすべて親クラスで行われるため、実際には関係ありません。新しい機能は次のとおりです。

template <class T>
class binSTree : public binTree<T> {
public:
    void insert (const T& newData) {
        if (root == NULL) {
            root = new binTreeNode<T>(newData);
        }
        else
            insert(root,newData);
    }
    bool search (const T& x) const {
        if (root != NULL)
            return search(root,x);
        else
            return false;
    }
    bool remove (const T& x) {
        if (root == NULL)
            return false;
        remove(root,x);
        return true;
    }
protected:
    binTreeNode<T>* root;
private:
    void insert (binTreeNode<T>*& ptr, const T& x) {
        if (ptr == NULL) {      // Base case, actual insertion
            binTreeNode<T>* newNode;
            newNode = new binTreeNode<T>(x);
            ptr = newNode;
            return;
        }
        if (x == ptr->data)
            return;
        else if (x < ptr->data)
            insert(ptr->left,x);
        else
            insert(ptr->right,x);
        return;
    }
    bool search (binTreeNode<T>* ptr, const T& x) const {
        if (ptr->data == x)
            return true;
        else if (x < ptr->data && ptr->left != NULL)
            search(ptr->left,x);
        else if (ptr->right != NULL)
            search(ptr->right,x);
        else
            return false;
    }
    binTreeNode<T>* remove (binTreeNode<T>* ptr, const T& x) {
        if (ptr == NULL)
            return NULL;
        else if (ptr->data == x && leaf(ptr)) {
            delete ptr;
            ptr = NULL;
            return ptr;
        }
        else if (ptr->data == x && !leaf(ptr))
            return ptr;
        else if (x < ptr->data) {
            ptr->left = remove(ptr->left,x);
            return ptr;
        }
        else {
            ptr->right = remove(ptr->right,x);
            return ptr;
        }
    }
    bool leaf (binTreeNode<T>* node) const {
        if (node->left != NULL || node->right != NULL)
            return false;
        return true;
    }
};

valgrind によると、セグメンテーション違反は、if (x == ptr->data) をチェックする条件のプライベート インサートにあります。これがなぜなのか誰にも分かりますか？完全に壁にぶち当たりました。ありがとう:3

4

1 に答える 1

4

コードには、クラッシュのremove原因である場合とそうでない場合がありますが、必ず修正する必要がある問題があります。ノードを再帰的に削除する場合、またはその結果としてノードが削除される場合は、親のorポインターも;に設定する必要があります。そうしないと、ダングリング ポインターに関連するエラーが発生する可能性があります。ptr->leftptr->rightleftrightNULL

于 2012-04-05T23:43:23.977 に答える