A maior rede de estudos do Brasil

como fazer algoritmos arvore binaria em c++ sem usar funções ja existente


2 resposta(s) - Contém resposta de Especialista

User badge image

RD Resoluções Verified user icon

Há mais de um mês

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

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
User badge image

Sabrina

Há mais de um mês

gente? vcs tem lista de exercícios já resolvidos de C++ ?

Essa pergunta já foi respondida por um dos nossos especialistas