Existem inúmeros algoritmos de árvore binária e inúmeras formas de fazer. Vamos começar por construir a árvore usando struct, com um campo para o valor, e um ponteiro para cada filho:
struct node {
int val;
node *esq,*dir;
node(int v=0) : val(v), esq(NULL), dir(NULL) {}
};
Agora vamos criar uma função para construir uma árvore de teste:
node* create_test()
{
node *root = new node(5);
root->esq = new node(4);
root->dir = new node(6);
root->esq->dir = new node(3);
return root;
}
E finalmente percorrer a árvore das três principais formas:
void pre(node* root)
{
cout << ' ' << root->val;
if(root->esq) pre(root->esq);
if(root->dir) pre(root->dir);
}
void in(node* root)
{
if(root->esq) in(root->esq);
cout << ' ' << root->val;
if(root->dir) in(root->dir);
}
void pos(node* root)
{
if(root->esq) pos(root->esq);
if(root->dir) pos(root->dir);
cout << ' ' << root->val;
}
Usando essa função principal:
int main() {
node* root = create_test();
cout << "Pre Order:"; pre(root); cout << endl;
cout << "In Order:"; in(root); cout << endl;
cout << "Pos Order:"; pos(root); cout << endl;
return 0;
}
Para obter essa saída:
Pre Order: 5 4 3 6 In Order: 4 3 5 6 Pos Order: 3 4 6 5
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar