Estrutura de Dados(Arvore Binaria)

Assuntos Gerais
#1

Alguem pode me ajudar a fazer uma comparação entre arvores Binarias em C++ utilizando template???

Grato pela atenção!!!

#2

Qual sua duvida?

#3 
template <class T> T* ArvoreBinaria <T> :: igual(ArvoreBinaria <T>*arv1, ArvoreBinaria <T>*arv2){
   No <T> *inicio1 = arv1->raiz;
   No <T> *inicio2 = arv2->raiz;
   
   if(arv1->getTotalNos() != arv2->getTotalNos()) {
       return 0;
   } else {
       while (inicio1 != NULL && inicio2 != NULL) {
           if (inicio1->valor == inicio2->valor){
               return igual(arv1,arv2);    
           } else if (inicio1->valor < inicio2->valor){
               inicio1 = inicio1->esquerdo;
               inicio2 = inicio2->esquerdo;
           } else{
               inicio1 = inicio1->direito;
               inicio2 = inicio2->direito;
           }
       } 
   }
   
   return NULL;
}

Minha duvida esta relacionada com recursividade, não conseguir entender como percorer uma arvore
utilizando recursividade, nesse exemplo de codigo eu tentei comparar duas arvores binarias mas pelo que
se pode perceber nem cheguei perto.

Como eu posso comparar duas arvores binarias, utilizando a recursividade???

#4

É algo mais ou menos assim:

bool igual(ArvoreBinaria <T>*arv1, ArvoreBinaria <T>*arv2){
   if ((arv1 == NULL) != (arv2 == NULL)) return false;
   if (arv1 == arv2) return true;

   if (arv1->valor != arv2->valor) return false;
   if (!igual(arv1->esquerda, arv2->esquerda)) return false;
   if (!igual(arv1->direita, arv2->direita)) return false;
   return true;
}

Observe que você NÃO DEVE usar o while. Ao invés disso faça a função chamar a si mesma (isso é a recursividade).

#5

[quote=victorwss]É algo mais ou menos assim:

bool igual(ArvoreBinaria <T>*arv1, ArvoreBinaria <T>*arv2){
   if ((arv1 == NULL) != (arv2 == NULL)) return false;
   if (arv1 == arv2) return true;

   if (arv1->valor != arv2->valor) return false;
   if (!igual(arv1->esquerda, arv2->esquerda)) return false;
   if (!igual(arv1->direita, arv2->direita)) return false;
   return true;
}

Observe que você NÃO DEVE usar o while. Ao invés disso faça a função chamar a si mesma (isso é a recursividade).[/quote]

Cara, obrigado pela ajuda, mas acontece que no meu codigo eu utilizo a classe No

template <class T>
class No {
    public : T valor;
             No *direito, *esquerdo;
             No ();
             No (const T&);
};

template <class T> No <T> :: No () {
    direito = esquerdo = NULL;
}

template <class T> No <T> :: No(const T& valor) {
    this->valor = valor;
    this->direito = this->esquerdo = NULL;
}

Sendo assim os ponteiros direito e esquerdo fazem parte dessa classe e não da arvore binaria.

Como seria se caso eu quisesse que o metodo [color=red]igual()[/color] se comportasse parecido com o metodo

da classe [color=darkred]String[/color] [color=blue]iguals()[/color].

Valeu mesmo cara.

Ha outra coisa, tem como alguem me indicar uma apostila, um exemplo, qualquer coisa sobre o algoritmo
de balanceamento de arvores chamado "DSW", porque eu procurei na net e so encontrei e um site, alguem conhece mais referencias???

#6