バイナリツリーを非再帰的に削除する際の問題

Question

Alex AllainのC++にジャンプは、バイナリ検索ツリーを非再帰的に削除するという驚くべきタスクを割り当てました（Ch.17）。私は、単に左と右のポインタではなく、の親ノードノードへのポインタを含むように、自分の構造体定義を変更することでこの作業を簡略化する方法を考え出しました。私はスタック/リンクリストのデータ構造を使用しないようにしています。これを達成するための

私のアルゴリズムは次のとおりですので、そのノードを削除し、親ノードに移動した場合、現在のノードのLとRのポインタが両方NULL

ある場合

1. をチェック。
2. ない場合は、ステップ1が達成されるまで、我々はNULLの親ノード（ルートノードのを打ってきたとき、私のアルゴリズムが終了
3. （L/Rポインタが両方占有されている場合は、左が最初になり）、LとRのノードにアクセスしてください親がNULL）

問題は、無限のwhileループに詰まってしまうことです。 私のinsert（）関数に欠陥があるのではないかと疑いますが、間違っている可能性があります。

次のコード、これまでに述べたすべての機能/構造を含む：

struct node 
{ 
    int key_value; 
    node *p_left; 
    node *p_right; 
    node *parent; 
}; 

node* insert (node *p_tree, int key, node* parent) 
{ 
    if (p_tree == NULL) 
    { 
     node* p_new_tree = new node; 
     p_new_tree->p_left = NULL; 
     p_new_tree->p_right = NULL; 
     p_new_tree->key_value = key; 
     p_new_tree->parent = parent; 
     return p_new_tree; 
    } 

    else if(key < p_tree->key_value) 
     p_tree->p_left = insert(p_tree->p_left, key, p_tree); 

    else 
     p_tree->p_right = insert(p_tree->p_right, key, p_tree); 

    return p_tree; 
} 

void destroy_tree_Iteratively(node* p_tree) 
{ 
    int nodesDestroyed = 0; //checking to see if I delete the right amount 

    while (p_tree != NULL) 
    { 
     if (p_tree->p_left == NULL && p_tree->p_right == NULL) 
     { 
      node* placeHolder = p_tree->parent; 
      delete p_tree; 
      p_tree = placeHolder; 
     } 
     else if (p_tree->p_left != NULL) 
      p_tree = p_tree->p_left; 
     else if (p_tree->p_right != NULL) 
      p_tree = p_tree->p_right; 
    } 

    cout << "You've deleted " << nodesDestroyed << " nodes!" << endl; 
} 

Answer 1

あなたは親からそのポインタをゼロにするために必要なノードを削除すると、それに左右のポインタのポイントの方。親がある場合。それ以外の場合、最初のifテストは決して真実ではなく、あなたはずっとトラバースし続けるでしょう。