4

BSTのすべての葉を無効にする関数を作成しました。もちろん、BSTには、左右のポインターと、ノードの値を格納するためのdataという文字があります。

void removeLeaves(struct Tree* T){
  if(T->left == NULL && T->right == NULL){
    printf("removing %c\n", T->data);
    T=NULL;
  }
  else{
    if(T->left!=NULL){
      removeLeaves(T->left);
    }
    if(T->right!=NULL){  
      removeLeaves(T->right);
    }
  }  
}

この関数を呼び出す前後にツリーを印刷します。また、上記のprintステートメントは機能し、無効化されたノードを出力しますが、結果のツリーは同じです。私は次のようなものを持っています：

print(BST);
removeLeaves(BST);
print(BST);

何が起こっているのか分かりますか？ありがとう。

4

3 に答える 3

1

Tを値で渡しているので、Tをnullに設定しても何も起こりません（Tはポインタのローカルコピーにすぎません）。

Tの「所有者」（つまり、親->左または親->右）をnullに設定する何らかの方法が必要です。

（また、Tをnullに設定すると、メモリリークのリスクがあります-free（）する必要がありますか？）

于 2012-06-01T05:15:02.183 に答える
1

T=NULL;ツリー内の何にもnullを割り当てず、ローカルポインタにnullを割り当てます。struct Tree **を変更できるように、を使用する必要がありstruct Tree *ます。

void removeLeaves(struct Tree ** T){
  if((*T)->left == NULL && (*T)->right == NULL){
    printf("removing %c\n", (*T)->data);
    *T = NULL;
  }
  else{
    if((*T)->left!=NULL){
      pruneTree((*T)->left);
    }
    if((*T)->right!=NULL){  
      pruneTree((*T)->right);
    }
  }  
}
于 2012-06-01T05:15:12.127 に答える
0

必要な部品があります。それは主にそれらを並べ替えることの問題です。

void removeLeaves(struct Tree* const T){
  if(T->left!=NULL){
    removeLeaves(T->left);
    T->left = NULL;
  }
  if(T->right!=NULL){  
    removeLeaves(T->right);
    T->right = NULL;
  }
}

ただし、に注意してくださいconst。あなたのコードはそれがなくても動作しますが、設定T = NULLは実際には何もしないので、動作しないはずです。

更新： @ PaulP.ROの答えは、ちなみに興味深いものです。私は私の方が好きですが、両方を試してどちらが適しているかを確認できます。

ちなみに、free()メモリリークを防ぐために、どこかでを呼び出す必要がないことを確認してください。

于 2012-06-01T05:19:43.210 に答える