Dúvida sobre Árvore Binária

Galera,

Estou a um tempo sem postar aqui no GUJ porque estou num corre-corre grande. Voltei ao minha rotina de estudos e agora surgiu uma dúvida. Estou estudando estrutura de dados e estou na parte de Arvores Binárias. Lendo uma apostila que eu peguei na net me deparei com um desafio interessante:

Transformar uma expressão(string) matemática em uma árvore.

Ex1.: x+y

+
/ \
x y

Ex2.: x+(y*z)

+
/ \
x *
/ \
y z

Como essa segunda arvore ficou mal desenhada vou explicar:
O nó (+) tem os filhos (x) e (*);
O nó (*) tem os filhos (y) e (z);

Como eu não sabia nada de árvores fiz a implementação dela, só que eu não consegui caminhar com o desafio acima. Sinceramente não consegui nem imaginar como fazer isso. Tô todo confuso! Podem me ajudar? Me deêm uma luz!

Vejam minha árvore:

public class ArvoreBinaria
{

    private int qNos;
    private int qNiveis;

    public void inserir(Celula raiz, char elemento)
    {

        if (elemento < raiz.getElemento())
        {
            if (raiz.getEsquerda() != null)
            {
                inserir(raiz.getEsquerda(), elemento);
            } else
            {
                System.out.println("Foi inserido  " + elemento + " a esquerda de  "
                        + raiz.getElemento());
                Celula c = new Celula(elemento);
                c.setPai(raiz);
                raiz.setEsquerda(c);
                System.out.println("O pai de " + elemento + " é:" + raiz.getElemento());
                System.out.println(" ");
            }
        } else if (elemento > raiz.getElemento())
        {
            if (raiz.getDireita() != null)
            {
                inserir(raiz.getDireita(), elemento);

            } else
            {
                System.out.println("Foi inserido  " + elemento + " a direita de "
                        + raiz.elemento);
                Celula c = new Celula(elemento);
                c.setPai(raiz);
                raiz.setDireita(c);
                System.out.println("O pai de " + elemento + " é:" + raiz.getElemento());
                System.out.println(" ");
            }
        }
    }

    public void preOrdem(Celula raiz)
    {
        if (raiz != null)
        {
            System.out.println("  Elemento: " + raiz.getElemento());
            preOrdem(raiz.getEsquerda());
            preOrdem(raiz.getDireita());
        }
    }

    public void emOrdem(Celula raiz)
    {
        if (raiz != null)
        {
            emOrdem(raiz.getEsquerda());
            System.out.println("  Elemento: " + raiz.getElemento());
            emOrdem(raiz.getDireita());
        }
    }    

    public void posOrdem(Celula raiz)
    {
        if (raiz != null)
        {
            posOrdem(raiz.getEsquerda());
            posOrdem(raiz.getDireita());
            System.out.println("  Elemento: " + raiz.getElemento());
        }
    }

    public int tamanho(Celula raiz)
    {
        if (raiz == null)
        {
            return 0;
        } else
        {
            this.qNos++;

            if (raiz.getDireita() != null)
            {
                this.qNos = 1 + somaTamanhoNos(raiz.getDireita());
            }
            if (raiz.getEsquerda() != null)
            {
                this.qNos = 1 + somaTamanhoNos(raiz.getEsquerda());
            }
        }

        return this.qNos;
    }

    private int somaTamanhoNos(Celula p)
    {

        if (p.getDireita() != null)
        {
            this.qNos = 1 + somaTamanhoNos(p.getDireita());
        }
        if (p.getEsquerda() != null)
        {
            this.qNos = 1 + somaTamanhoNos(p.getEsquerda());
        }
        return this.qNos;
    }

    public int altura(Celula raiz)
    {
        if (raiz == null)
        {
            return 0;
        } else
        {
            Celula c = raiz;
            if (c.getDireita() != null)
            {
                this.qNiveis++;
                this.altura(c.getDireita());
            } else if (c.getEsquerda() != null)
            {
                this.qNiveis++;
                this.altura(c.getEsquerda());
            }
        }

        return this.qNiveis;
    }

    public boolean cheia(Celula raiz)
    {
        boolean resultado = true;

        return resultado;
    }

    
    public boolean cheio(Celula raiz)
    {
        boolean cheio = false;

        if ((2 ^ this.altura(raiz)) == (this.tamanho(raiz) - 1))
        {
            cheio = true;
        }

        return cheio;
    }

public class Celula {

    Celula esquerda;
    Celula direita;
    Celula pai;
    char elemento;

    public Celula(char value) {
        this.elemento = value;
    }

    public Celula getDireita() {
        return direita;
    }

    public void setDireita(Celula direita) {
        this.direita = direita;
    }

    public char getElemento() {
        return elemento;
    }

    public void setElemento(char elemento) {
        this.elemento = elemento;
    }

    public Celula getEsquerda() {
        return esquerda;
    }

    public void setEsquerda(Celula esquerda) {
        this.esquerda = esquerda;
    }

    public Celula getPai()
    {
        return pai;
    }

    public void setPai(Celula pai)
    {
        this.pai = pai;
    }

1 Resposta

Topicos relacionados