Árbol de búsqueda binario de C ++ Insertar a través de recursión

Question

Así que mi código está abajo. No recibo ningún error y coloca todo en el nodo muy bien. Pero según mis declaraciones de depuración Cada vez que se inserta algo, se encuentra la raíz. No estoy seguro si eso es correcto. Pero de acuerdo con el archivo de salida de la asignación, mis respuestas son diferentes cuando se trata de la altura del árbol, los recorridos y, simplemente, todavía tengo problemas con mi función de recuento de hojas. Sin embargo, otra historia.

Según las declaraciones de depuración, parece que todo va bien donde deberían. Pero creo que podría necesitar ojos nuevos. No veo cómo mis recorridos podrían cambiar en absoluto, ya que es solo una cuestión de dónde estoy procesando el nodo que debería afectar el orden, el orden y el orden.

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;
               }
        }
 }

Mi función de altura es la siguiente en caso de que mi inserción esté realmente 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

Debe cambiar la redacción de sus declaraciones de depuración

Realmente debería leer (no el nodo raíz)

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

Es solo la raíz cuando se llama por primera vez después de que cualquier llamada con node- > left o node- > right lo convierte en un nodo intermedio.

Para escribir altura () haría esto:

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

Debe comenzar con su raíz iniciada a nula. Además, está pasando * & amp; node en; debería ser * nodo. De lo contrario, está pasando un puntero a la dirección (o referencia, no estoy seguro de cuál en este contexto, pero ambos no van a estar bien). Debería pasarle un puntero a Node, no una referencia.

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:
Debe ser un puntero a los punteros izquierdo / derecho / raíz (es decir, un puntero doble), por lo que el código publicado es correcto, aunque algo claro.

@Doug:
Considere cambiar su función de inserción de esta manera:

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;
       }

Aclara su intención de cambiar el puntero pasado como primer parámetro (o más bien, el puntero cuya dirección se pasará como primer parámetro). Esto ayudará a evitar confusiones como la que acaba de ocurrir. .

Las llamadas a este inserto (), como:

insert(&root, newNode);

también reflejará su intención de cambiar el valor del puntero. Sin embargo, esto es una cuestión de estilo, así que no puedo discutir si no quieres cambiar.

---

En cuanto a verificar si el árbol es " correcto, " ¿Por qué no sacarlo y ver por ti mismo? Algo a lo largo de las líneas 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);
}

(Código no probado)