C++ Insérer un arbre de recherche binaire via la récursivité

Question

Donc, mon code est ci-dessous. Je ne reçois aucune erreur et tout se passe bien dans le nœud. Mais en fonction de mes instructions de débogage Chaque fois que quelque chose est inséré c'est la racine. Je ne suis pas sûr que ce soit juste. Mais selon le fichier de sortie pour l'assignation, mes réponses sont différentes quand il s'agit de la hauteur de l'arbre, les traversées, et j'ai juste des problèmes avec la fonction de comptage des feuilles. Une autre histoire cependant. En fonction des instructions de débogage, il semble que tout se passe comme prévu. Mais je me dis que je pourrais avoir besoin de nouveaux yeux. Je ne vois pas comment mes traversées pourraient changer du tout puisque c'est vraiment une question d'endroit où je suis en train de traiter le nœud qui devrait affecter l'Inorder, la pré-commande et la post-commande.

template <class T> 
void BT<T>::insert(const T& item) 
{ 
    Node<T>* newNode; 
    newNode = new Node<T>(item); 
    insert(root, newNode); 
} 


template <class T> 
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode) 
{ 
    if (root == NULL) 
     { 
      cout << "Root Found" << newNode->data << endl; 
      root = newNode; 
     } 
    else 
     { 
      if (newNode->data < root->data) 
       { 
       insert(root->left, newNode); 
       cout << "Inserting Left" << newNode-> data << endl; 
       } 
      else 
       { 
       insert(root->right, newNode); 
       cout << "Inserting Right" << newNode->data << endl; 
       } 
     } 
} 

Ma fonction de hauteur est la suivante juste au cas où mon insertion est réellement bonne.

template <class T> 
int BT<T>::height() const 
{ 
    return height(root); 
} 


    template <class T> 
    int BT<T>::height(Node<T>* root) const 
    { 
    if (root == NULL) 
     return 0; 
    else 
     { 
     if (height(root->right) > height(root->left)) 
     return 1 + height(root-> right); 
     return 1 + height(root->left); 
     } 
    } 

Answer 1

Vous devez modifier le libellé de vos déclarations de débogage

Vraiment il faut lire (non nœud racine)

cout << "Leaf Node Found" << newNode->data << endl; 

Il est seulement la racine quand il est d'abord appelée après que tout call with node-> left ou node-> right en fait un noeud intermédiaire.

Pour écrire la hauteur() je ferais ceci:

template <class T> 
int BT<T>::height(Node<T>* root) const 
{ 
    if (root == NULL) {return 0;} 

    return 1 + max(height(root->left),height(root->right)); 
} 

Answer 2

Vous devez commencer avec votre racine init'd à null. En outre, vous passez le nœud * & dans; ça devrait être * noeud. Sinon, vous passez un pointeur vers l'adresse (ou référence, je ne suis pas sûr de ce que dans ce contexte, mais les deux ne vont pas avoir raison). Vous devriez passer un pointeur vers Node in, pas une référence.

template <class T> 
void BT<T>::BT() 
{ root = 0;} 

template <class T> 
void BT<T>::insert(const T& item) 
{ 
    Node<T>* newNode; 
    newNode = new Node<T>(item); 
    insert(root, newNode); 
} 

template <class T> 
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode) 
{ 
/*stuff*/ 
} 

Answer 3

@Vlion:
Il doit être un pointeur vers la gauche/droite/pointeurs de racines (à savoir un double pointeur), de sorte que le code affiché est correct, bien que pas très claire.

@Doug:
Pensez à modifier la fonction d'insertion ainsi:

template <class T> 
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode) 
{ 
    if (*root == NULL) 
     { 
      cout << "Root Found" << newNode->data << endl; 
      *root = newNode; 
     } 

Il indique clairement votre intention que vous changerez le pointeur passé comme premier paramètre (ou plutôt, le pointeur dont l'adresse sera être passé comme le premier paramètre.) Cela aidera à éviter la confusion comme celle qui vient de se produire.

Les appels à cet insert(), tels que:

insert(&root, newNode); 

refléteront également votre intention de changer la valeur du pointeur. C'est une question de style, cependant, je ne peux pas discuter si vous ne voulez pas changer. Pour vérifier si l'arbre est "correct", pourquoi ne pas le dessiner et voir par vous-même?Quelque chose le long des lignes de:

template class<T> 
void printTree(struct Node<T>* node, int level=0) 
{ 
    if (!node) { 
     for (int i=0; i<level; ++i) 
      cout << " "; 
     cout << "NULL" << endl; 

     return; 
    } 

    printTree(node->left, level+1); 

    for (int i=0; i<level; ++i) 
     cout << " "; 
    cout << node->data << endl; 

    printTree(node->right, level+1); 
} 

(code non testé)