Yinelenen bir ikili ağaç silme ile ilgili sorun

Question

Alex Allain'in C++ içine atlamak bana yinelenen bir ikili arama ağacını silme konusunda inanılmaz bir görev verdi (Bölüm 17). Yapım tanımımı değiştirerek bu görevi basitleştirmenin bir yolunu buldum. Böylece, sadece sol ve sağ işaretçiler yerine ana düğümüne bir işaretçi eklenmiştir. Bir yığın/bağlantılı liste veri yapısı kullanmaktan kaçınmaya çalışıyorum. Bu başarmak için

Benim algoritmadır:

1. denetleme geçerli düğümün L ve R işaretçileri hem NULL
2. ise böylece düğüm silip ana düğüme gidin. 1. adım elde edilene kadar, L ve R düğümlerine gitmek Değilse
3. biz BOŞ ebeveyn düğüm (kök düğüm en hit ettik zaman
4. Benim algoritması sonucuna (sol L/R işaretçileri hem işgal birinci eğer gider) üst = NULL)

Sorun şu ki, sonsuz bir döngüde takılıyorum. Benim insert() işlevimin bozuk olduğundan şüpheliyim, ama yanılıyor olabilirim.

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

Eğer ebeveynden kendi işaretçi, sıfırlamamaktadır gereken bir düğüm sildiğinizde sol ve sağ işaretçileri noktalarının hangisi ona:

Aşağıdaki kod şimdiye kadar bahsedilen tüm fonksiyonları/yapıları kapsamaktadır . Bir ebeveyn varsa. Aksi takdirde, ilk if testi asla doğru olmaz ve sonsuza kadar geçiş yapmaya devam edersiniz.