2分探索木の全てのノードを削除する関数を作りたい

Question

Node * BinaryTree::removeAll(Node *r) { //定義が不明....

	Node *removed;
	if (root == NULL)
		return NULL;

	if (r->left) {
		if (r->left->left)
			return removeAll(r->left->left);
		else if (r->left->right)
			return removeAll(r->left->right);
		else {
			removed = r->left;
			cout << "deleted : " << r->left->data << endl;
			delete removed;
			r->left = NULL;
			return removeAll(root);
		}
	}
	else if (r->right) {
		if (r->right->left)
			return removeAll(r->right->left);
		else if (r->right->right)
			return removeAll(r->right->right);
		else {
			removed = r->right;
			r->right = NULL;
			cout << "deleted : " << r->right->data << endl;
			delete removed;
			return removeAll(root);
		}
	}
	else {
		removed = r;
		cout << "deleted : " << r->data << endl;
		r = NULL;
		delete r;
	}
	return removeAll(root);
}

2分探索木のノードを全て削除する関数を定義したいのですが、どうしてもエラーが出てしまいます。

Answer 1

デストラクタ使う案は、正直オススメしないです。その環境で動作することは事実ですが、全ての環境で動作する保証はないですし、外部から使えるクラスでnew確保に依存する設計は、あまり綺麗ではないです。

void BinaryTree::removeAll() {
    removeBranch( root );
    delete root;
    root = nullptr;
}

void BinaryTree::removeBranch(Node *r) {
    if (!r) return;

    removeBranch( r->left );
    removeBranch( r->right );
    delete r->left;
    delete r->right;
}

これで動作しませんか?

Comments

[majiponi]

removeBranch関数の中の、removeAll関数呼びだし、removeBranchの誤植です。

Answer 2

void BinaryTree::removeAll()
{
  void remove(Node* p)
  {
    if(p){
      remove(p->left);
      remove(p->right);
      delete p;
    }
  }
  remove(root);
}

動作未確認、Nodeクラスのデストラクタを用意しておくというのもありですね。

Answer 3

Node::~Node() {
    if (this == NULL)
        return;

    delete left;
    delete right;
}

としておき、

delete root;

すれば、再帰的に全てのノードを削除できます。

失礼しました。これで再帰的に全てのノードを削除できます。

Node::~Node() {
    if (left != NULL)
        delete left;

    if (right != NULL)
        delete right;
}

// どこかで
if (root != NULL)
    delete root;

Comments

[HogeAnimalLover]

「デストラクタ使うのもアリ」と書いたら時間差で回答されていましたｗところでthis == NULLって条件なりたちえるんですかね・・・

[naomi3]

動作確認しました。OKです。

[Chironian]

横から失礼します。

↓に「メンバ関数内で(this == NULL)の意味はあるのか?」のQAがありました。
http://stackoverflow.com/questions/1844005/checking-if-this-is-null
NULLポインタ経由のメンバ関数呼び出しは「未定義」だそうです。
つまり、コンパイラによって意図通り動作したりしなかったりすると言うことです。

ところで、デストラクタの場合は話は簡単です。deleteにNULLポインタが渡された場合、デストラクタは呼ばれませんので、デストラクタがthis==NULLで呼ばれる可能性は事実上ないです。
http://washieagle.blogspot.jp/2010/02/cnulldelete.html