0

min 要素を削除するための次の関数があります。

int BinaryTree::delete_min_helper(TreeNode *node){

   while(node->left != NULL){
     node = node->left;
   }

   if(node == root){
     return 1;
   }

   delete node;
   node = NULL;
   return 0;
}

この関数には常にルート ノードへのポインターを渡します。私はこれといくつかのバリエーションを試しましたが、常に間違ったものを削除するか、何も削除しないようです. 理由はありますか？

コンパイル可能な例を次に示します。

#ifndef _TREE_H_
#define _TREE_H_

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct TreeNode {
  int val;
  char *str;
  TreeNode *left;
  TreeNode *right;
};

class BinaryTree {
  public:

 BinaryTree();
 ~BinaryTree();

 int insert_node(unsigned int val, char *str);
 TreeNode *find_min();
 int delete_min();
 void print();

 private:

 int insert_node_helper(TreeNode *&node, unsigned int val, char *str);
 int delete_min_helper(TreeNode *node);
 void print_helper(TreeNode *node);

 TreeNode *root;  
};

#endif

BinaryTree::BinaryTree(){
  this->root = NULL;
}


BinaryTree::~BinaryTree(){
}

int BinaryTree::insert_node(unsigned int val, char *str){
  return insert_node_helper(this->root, val, str);
}

int BinaryTree::insert_node_helper(TreeNode *&node, unsigned int val, char *str){

  if(node == NULL){
    node = new TreeNode;
    node->val = val;
    node->str = strdup(str);
    node->left = NULL;
    node->right = NULL;
    if(node != NULL){
      return 0;
    }else{
      puts("inserted null node");
      return 1;
   }
 }else if(val <= node->val){
   return insert_node_helper(node->left, val, str);
 }else if(val > node->val){
   return insert_node_helper(node->right, val, str);
 }

 return 1;
}

void BinaryTree::print(){
  print_helper(this->root);
}


void BinaryTree::print_helper(TreeNode *node){

    if(node != NULL){
      print_helper(node->right);
      printf("%d occurrences of \"%s\"\n", node->val, node->str);
      print_helper(node->left);
    }

}

TreeNode *BinaryTree::find_min(){
  TreeNode *temp = this->root;
  while(temp->left != NULL){
    temp = temp->left;
  }
  return temp;
}

int BinaryTree::delete_min(){
   return delete_min_helper(root);
}

int BinaryTree::delete_min_helper(TreeNode *node){

   while(node->left != NULL){
     node = node->left;
   }

  if(node == root){
    puts("attempted to delete root");
    return 1;
  }

  delete node;
  node = NULL;
  return 0;
}

#include <time.h>

int main(){

  BinaryTree bt;

  srand(time(NULL));
  for(int i = 0; i < 10; i++){
     bt.insert_node(rand() % 20, "test");
  }

  bt.print();
  printf("min val = %d\n", bt.find_min()->val);
  puts("#################################");
  bt.delete_min();
  bt.print();
  printf("min val = %d\n", bt.find_min()->val);

  return 0;
}
4

1 に答える 1

4

ポインターへの参照を引数 ( TreeNode *&node) として取得し、それを変更しています。したがって、ツリーのルートをこのメソッドに渡すと、最終的にルートが に設定されNULLます。

さらに、ポインターを NULL に設定した後に delete を呼び出し、null ポインターで呼び出されても何もしないため、これは実際にはまったく何も削除deleteしません。

元の投稿の編集後の更新:

rootBinaryTree のメンバーだと思います。Short, Self Contained, Compilable Exampleを投稿すると、より簡単に支援できます。

あなたはまだ参考として定着しています。したがって、常に真であり、ステートメントnode == rootに到達することはありません。deleteしたがって、実際には何も削除していませんが、ルートを一番左の子ノードに変更しています。

メソッドの署名を次のように変更してみてください

int BinaryTree::delete_min_helper(TreeNode *node){

つまり、アンパサンド ( &) はありません。

編集後:

さて、あなたのプログラムを実行したところ、2 番目の問題が見つかりました。ラインで

node = NULL;

left親ノードのポインターではなく、ローカルポインターの値を変更しています。これは、次にツリーをトラバースするときに、削除したばかりのメモリへのポインターにアクセスすることを意味します。それは未定義の動作を引き起こします。これを回避するにはleft、リーフ ノードを削除するときに、親ノードの -pointer を 0 に設定する必要があります。

于 2013-02-07T22:53:09.283 に答える