How to create a tree with n children per node?

Asked

Viewed 1,409 times

-1

I would like to know how to implement a tree where each node can have n children?

As in the example below: diagrama da árvore

Only in case the nodes would be an instance of a class.

EDITED

I’m trying to do this with a ArrayList, but I don’t understand how to insert a ArrayList within a ArrayList recursively or interactively even because the tree has no defined limit.

Example: How to insert and pick the value 7? Type will have the ArrayList pro at the root (8) and will have the ArrayList pro first node of root node (the 4).

java
  • 2

    Start with that: public class No { private List<No> nos; /* ... */ }.

  • Array if it has a limit. But if you are dealing with Arvore Trie or Patricia, you use a chain list, with the father pointing to the first child.

  • I edited the question to better illustrate my doubt.

1 answer

4

I’m trying to do this with a ArrayList, but I don’t understand how to insert a ArrayList within a ArrayList recursively or interactively even because the tree has no defined limit.

That’s not what you should do. That’s a XY problem.

Java is an object-oriented language. Keeping recursive lists of numbers is not an object-oriented way to attack your problem. This means that this approach probably won’t work. If you can make it work, the result will be a huge gambit.

The best way would be to see what are the objects involved in this:

  1. You have a Arvore.

  2. To Arvore has a No root.

  3. Each No can have several other Nos below it.

  4. Each No holds a whole number.

Turning these four requirements into code:

public class Arvore {
    private No raiz;
}

import java.util.List;

public class No {
    private int conteudo;
    private List<No> filhos;
}

Ok, now that we have the general structure of our classes, let’s define some methods and constructors:

public class Arvore {
    private No raiz;

    public Arvore(int conteudoRaiz) {
        this.raiz = new No(conteudoRaiz);
    }

    public No getRaiz() {
        return raiz;
    }

    public No buscar(int procurado) {
        raiz.buscar(procurado);
    }
}

import java.util.ArrayList;
import java.util.List;

public class No {
    private int conteudo;
    private List<No> filhos;

    public No(int conteudo) {
        this.filhos = new ArrayList<>();
        this.conteudo = conteudo;
    }

    public No acrescentarFilho(int conteudoFilho) {
        No n = new No(conteudoFilho);
        filhos.add(n);
        return n;
    }

    public int getConteudo() {
        return conteudo;
    }

    public List<No> getFilhos() {
        return filhos;
    }

    public No buscar(int procurado) {
        if (procurado == conteudo) return this;
        for (No filho : filhos) {
            No achou = filho.buscar(procurado);
            if (achou != null) return achou;
        }
        return null;
    }
}

You can go on adding other methods to accomplish the jobs you want, but the point here is that you have to have well defined what each thing is. Say a tree is a list or a node of a tree is a list just leaves things complicated and confusing and probably won’t work. Ideally say the tree has a root knot, that one knot has a list of other nodes. Note that the verb is important: the concept if was and had completely changes the way you will structure your code.

Browser other questions tagged java

You are not signed in. Login or sign up in order to post.