Recursive binary tree and sum of leaves

Friends I'm having trouble solving this exercise, and I don't know how to do it anymore. I got to implement the tree with recursion, but I could not leave the node empty and some sheets with number, as the exercise. Next I need to add up the items that are on the sheets.

No.java 

public class No {

    public int valor;
    public No direito;
    public No esquerdo;

    public No(int valor) {
        this.valor = valor;
    }
}

ArvoreBinaria.java 

public class ArvoreBinaria {

    private No raiz;

    public void inserir(int valor) {
        if (raiz == null) {
            raiz = new No(valor);
        } else {
            No novo = new No(valor);
            inserir(raiz, novo);

        }

    }

    private void inserir(No arvore, No novo) {
        if (novo.valor > arvore.valor) {
            if (arvore.direito == null) {
                arvore.direito = novo;
            } else {
                inserir(arvore.direito, novo);
            }
        } else {
            if (arvore.esquerdo == null) {
                arvore.esquerdo = novo;
            } else {
                inserir(arvore.esquerdo, novo);
            }
        }
    }

Exercise 

- Uma árvore tem nós;
- Um nó pode ou não ter outros nós;
- Um nó, não folha, tem sempre um nó do lado direito e outro do lado esquerdo
- As folhas não tem nós abaixo;
- As folhas têm associado um número inteiro

The following figure represents 3 instances of trees binary

binary trees

We intend to implement an algorithm in Java that allows instance construction of this type. You should have a method that returns the sum of the tree, i.e. the sum of the leaves.

Tips:

  • a node, not a leaf, always has a node on the left and a node on the right
  • after the construction of a node, it will be possible to add other nodes
  • Recursion
  • do not use Java type complexes (HashMap s, List s and etc)
Author: Victor Stafusa, 2017-10-29
Source

1 answers

Here goes your binary tree class. I added in class No and Class ArvoreBinaria the methods soma(). I also put the toString() to be able to show the structira of the tree.

class ArvoreBinaria {

    private No raiz;

    public void inserir(int valor) {
        if (raiz == null) {
            raiz = new No(valor);
        } else {
            No novo = new No(valor);
            inserir(raiz, novo);
        }
    }

    private void inserir(No arvore, No novo) {
        if (novo.valor > arvore.valor) {
            if (arvore.direito == null) {
                arvore.direito = novo;
            } else {
                inserir(arvore.direito, novo);
            }
        } else {
            if (arvore.esquerdo == null) {
                arvore.esquerdo = novo;
            } else {
                inserir(arvore.esquerdo, novo);
            }
        }
    }

    public int soma() {
        return raiz == null ? 0 : raiz.soma();
    }

    @Override
    public String toString() {
        return raiz == null ? "*" : raiz.toString();
    }

    private static class No {

        private int valor;
        private No direito;
        private No esquerdo;

        public No(int valor) {
            this.valor = valor;
        }

        public int soma() {
            return valor
                    + (direito == null ? 0 : direito.soma())
                    + (esquerdo == null ? 0 : esquerdo.soma());
        }

        @Override
        public String toString() {
            return (esquerdo == null ? "*" : "(" + esquerdo + ")")
                    + valor
                    + (direito == null ? "*" : "(" + direito + ")");
        }
    }
}

Here is a test class: 

class Teste {
    public static void main(String[] args) {
        ArvoreBinaria ab = new ArvoreBinaria();
        System.out.println(ab);
        ab.inserir(5);
        System.out.println(ab);
        ab.inserir(10);
        System.out.println(ab);
        ab.inserir(15);
        System.out.println(ab);
        ab.inserir(2);
        System.out.println(ab);
        ab.inserir(4);
        System.out.println(ab);
        ab.inserir(6);
        System.out.println(ab);
        ab.inserir(8);
        System.out.println(ab);
        ab.inserir(20);
        System.out.println(ab);
        System.out.println(ab.soma());
    }
}

Here is the output: 

*
*5*
*5(*10*)
*5(*10(*15*))
(*2*)5(*10(*15*))
(*2(*4*))5(*10(*15*))
(*2(*4*))5((*6*)10(*15*))
(*2(*4*))5((*6(*8*))10(*15*))
(*2(*4*))5((*6(*8*))10(*15(*20*)))
70

Note from the output that the tree is being assembled as expected and that the sum is also correct.

See here working on ideone.

 4
Author: Victor Stafusa, 2017-10-29 22:10:39