Insertion d'arborescence de recherche binaire C ++ via la récursivité

Question

Donc, mon code est ci-dessous. Je ne reçois aucune erreur et cela place tout dans le nœud correctement. Mais en fonction de mes instructions de débogage Chaque fois que quelque chose est inséré, il trouve la racine. Je ne sais pas si c'est vrai. Mais selon le fichier de sortie de l'affectation, mes réponses sont différentes en ce qui concerne la hauteur de l'arbre, les traversées, et je ne fais que plat, j'ai toujours des problèmes avec ma fonction de comptage de feuilles. Une autre histoire cependant.

Sur la base des instructions de débogage, tout se passe comme il se doit. Mais je suppose que je pourrais avoir besoin de nouveaux yeux. Je ne vois pas comment mes traversées pourraient changer du tout, car ce n'est qu'une question de savoir où je traite le nœud qui doit affecter l'ordre, 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 irait bien.

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 instructions de débogage

Vraiment, il devrait lire (pas le nœud racine)

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

Ce n’est que la racine lorsqu’il est appelé pour la première fois après que tout appel avec noeud - > left ou noeud - > right en fasse un noeud intermédiaire.

Pour écrire height (), je voudrais faire 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. De plus, vous passez * & amp; node dans; ce devrait être * noeud. Sinon, vous passez un pointeur sur l'adresse (ou la référence, je ne sais pas lequel dans ce contexte, mais les deux ne vont pas être corrects). Vous devriez passer un pointeur sur 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 s'agir d'un pointeur sur les pointeurs gauche / droit / racine (c'est-à-dire un double pointeur), de sorte que le code publié est correct, bien qu'un peu incertain.

@Doug:
Pensez à changer votre 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;
       }

Cela indique clairement votre intention de changer le pointeur passé en tant que premier paramètre (ou plutôt, le pointeur dont l'adresse sera passée en tant que premier paramètre). Cela vous évitera des confusions telles que celle qui vient de se produire. .

Les appels à cette insertion (), tels que:

insert(&root, newNode);

reflétera également votre intention de changer la valeur du pointeur. C'est une question de style, donc je ne peux pas discuter si vous ne voulez pas changer.

Pour ce qui est de vérifier si l’arbre est " correct, " pourquoi ne pas le dessiner et voir par vous-même? Quelque chose dans le genre 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é)