C++ Binaires de Recherche Arbres Insérer via la Récursivité

Donc mon code est ci-dessous. Je ne reçois pas toutes les erreurs et elle met tout dans le nœud de l'amende juste. Mais, d'après mon des instructions de débogage à Chaque fois que quelque chose est insérée c'est de trouver la racine. Je ne suis pas sûr si c'est à droite. Mais selon le fichier de sortie pour l'affectation, mes réponses sont différentes quand il s'agit de la hauteur de l'arbre, la traversals, et je viens de plat suis toujours avoir des problèmes avec ma leaf fonction count. Une autre histoire cependant.

Basé sur les instructions de débogage on dirait que tout est d'aller là où ils le devraient. Mais je me dis que je pourrait avoir besoin d'un regard neuf. Je ne vois pas comment mon traversals pourrait changer puisque c'est vraiment qu'une question de là où je suis proccessing le nœud qui doit procéder à la Afinde, précommande, et postorder.

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 comme suit juste au cas où mon insert est en fait très 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);
      }
   }

InformationsquelleAutor Doug | 2008-10-16

binary-tree c++insert

5

Vous avez besoin de modifier le libellé de vos instructions de débogage

Vraiment, il devrait lire (pas de nœud Racine)
```
 cout << "Leaf Node Found" << newNode->data << endl;
```
Il n'est que la racine quand il est d'abord appelée après que tout appel avec noeud->gauche ou noeud->droite fait un nœud intermédiaire.

À écrire de hauteur (en) je voudrais faire cela:
```
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));
}
```
- si vous pensez que mon insert est correct? Je veux dire basé sur mon debug imprime... et physiquement écrit ce vers le bas... tout semble correspondre.
- Ouais la hauteur de votre m'a donné la même valeur que la mienne. Il semble plus propre et plus efficace bien que si je l'apprécie.
- Un peu de correction, si(racine = NULL) doit être racine == NULL.
InformationsquelleAutor Martin York
0

Vous avez besoin pour commencer à la racine de votre init avais à null. Aussi, vous êtes de passage *&nœud; il devrait être *nœud. Autre chose, vous êtes en passant un pointeur vers l'adresse(ou de référence, je ne suis pas sûr de qui, dans ce contexte, mais les deux ne vont pas être de droite). Vous devriez être en train de passer un pointeur vers le Nœud dans, 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*/
}
```
- Non, il a besoin de la référence à procéder à la cession de travailler correctement. Si elle est moche je vais vous donner.
InformationsquelleAutor Paul Nathan
0

@Vlion:

Il doit être un pointeur vers la gauche/la droite/la racine des pointeurs (c'est à dire un double pointeur), de sorte que le posté code est correct, bien qu'un peu floue.

@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;
       }
```
Il fait clairement votre intention que vous allez être en train de changer le pointeur passé comme premier paramètre (ou plutôt, le pointeur dont l'adresse sera passée comme premier paramètre.) Il permettra d'éviter la confusion tels que celui qui vient de se passer.

Les appels à cette insert(), tels que:
```
insert(&root, newNode);
```
tiendra aussi compte de votre intention de modifier la valeur du pointeur. C'est une question de style, cependant, de sorte que je ne peux pas discuter si vous ne voulez pas changer.

Comme pour vérifier si l'arbre est "correct", pourquoi ne pas tirer et de 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é)
- Merci pour l'aide. Je vais donc essayer changeing autour comme vous l'avez dit, mais, techniquement, notre code est en train de faire la même choses bien droit?
- J'ai aussi oublié d'ajouter que, bien que je n'ai pas aller aussi loin que vous avez à faire une fonction de dessin de l'arbre, Basé sur le debug imprime, et mon propre dessin de la pré-définies codé en dur numéros insérés.. Il semble être le faire correctement. Je l'ai envoyée à ma TA, dans l'espoir qu'il peut préciser.
- Oui, ils sont tous les deux à faire la même chose; la différence est cosmétique. Le code est correct, le problème est (comme Martin York a souligné que l'impression de "root trouvé" alors que le nœud est la racine de la nouvelle arborescence. (c'est à dire une feuille)
InformationsquelleAutor aib

Vous devez vous connecter pour publier un commentaire.