C ++ Inserção de árvore de pesquisa binária por recursão

Question

Então, meu código está abaixo. Não estou recebendo erros e isso coloca tudo bem no nó. Mas, com base nas minhas declarações de depuração toda vez que tudo é inserido, está encontrando a raiz. Não tenho certeza se isso está certo. Mas, de acordo com o arquivo de saída para a atribuição, minhas respostas são diferentes quando se trata da altura da árvore, dos Traversals, e eu ainda estou tendo problemas com minha função de contagem de folhas. Outra história embora.

Com base nas declarações de depuração, parece que tudo está indo bem onde deveriam. Mas acho que posso precisar de olhos frescos. Não vejo como meus travessos podem mudar, pois é realmente apenas uma questão de onde estou procedendo o nó que deve efetuar a encomenda, a pré -encomenda e a encomenda.

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

Minha função de altura é a seguinte, caso minha inserção esteja realmente bem.

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

Você precisa alterar a redação de suas declarações de depuração

Realmente deveria ler (não o nó raiz)

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

É apenas a raiz quando é chamado pela primeira vez depois que qualquer chamada com nó-> esquerda ou nó-> direita o torna um nó intermediário.

Para escrever altura () eu faria isso:

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

Você precisa começar com seu início de raiz para nulo. Além disso, você está passando *& nó; deve ser *nó. Caso contrário, você está passando um ponteiro para o endereço (ou referência, não tenho certeza de qual neste contexto, mas ambos não estarão certos). Você deve passar um ponteiro para o nó, não uma referência.

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:
Deve ser um ponteiro para os ponteiros esquerda/direita/raiz (ou seja, um ponteiro duplo), então o código postado está correto, embora um pouco claro.

@Doug:
Considere alterar sua função de inserção assim:

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

Isso deixa claro sua intenção que você mudará o ponteiro passado como o primeiro parâmetro (ou melhor, o ponteiro cujo endereço será passado como o primeiro parâmetro.) Isso ajudará a evitar confusão como a que acabou de acontecer.

As chamadas para este insert (), como:

insert(&root, newNode);

também refletirá sua intenção de alterar o valor do ponteiro. Porém, isso é uma questão de estilo, por isso não posso argumentar se você não quer mudar.

---

Quanto a verificar se a árvore está "correta", por que não desenhá -la e ver por si mesmo? Algo parecido com:

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 não testado)