Recursive binary tree and sum of leaves

Question

Recursive binary tree and sum of leaves

Navigation

#1 by (4 votes)

4

Friends I'm having trouble resolving this exercise, and I do not know how else to do it. I got to implement the tree with recursion, but I could not leave the Knot empty and some sheets with number, according to the exercise. Then I need to add the items that are in the sheets.

Nojava

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 binary trees

It is intended to implement an algorithm in Java that allows the instantiation of this type. You should have a method that returns the sum of the tree, that is the sum of the leaves.

Tips:

A node, not leaf, always has a node to the left and a node to the right
After building a node, you can add other nodes
Recursion
Do not use Java complex type (% with% s,% with% s and etc)

java

asked by anonymous 29.10.2017 / 22:22

1 answer

What is the difference between Type-safe and Null-safe? Does URL size influence search engine rankings?

score 4 · Accepted Answer

Here's your binary tree class. I added the No and the ArvoreBinaria classes to soma() methods. I also put toString() to show the structure 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's 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's 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

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

See here working on ideone.