How do you go through a binary tree?

Question

I’m having trouble adding an element to a binary tree because I don’t know how to go...

Tree knot

public class NodeBinaryTree extends BinaryTree{
    NodeBinaryTree left;
    NodeBinaryTree right;
    int elemento;

    public NodeBinaryTree(int elemento){
        this.elemento = elemento;
        left = right = null;
    }

}

Tree structure

public class BinaryTree {
    NodeBinaryTree root;


    public BinaryTree(){
        root = null;
    }

    public boolean isEmpty(){
        return root == null;
    }

    public void add(int elemento, NodeBinaryTree arvore){
        NodeBinaryTree aux = new NodeBinaryTree(elemento);
        if(isEmpty()){
            root = aux;
        }else{
            aux = aux.left;
            //quero percorrer a arvore em pré ordem
        }
    }



}

Answer 1

When using a binary tree it is assumed that you can compare the elements. If this is not possible you need another data structure. The algorithm is very simple:

Se a árvore A está vazia
    Construir nova árvore A com o item I como nó e subárvores vazias
Caso contrário
    Se o valor do item I for menor ao do nó
        Se a subárvore a esquerda estiver vazia
            Construir nova subárvore E a esquerda com I como nó e subárvores vazias
        Caso contrário 
            Inserir I na subárvore à esquerda
    Caso contrário
        Se a subárvore a direita estiver vazia
            Construir nova subárvore D a direita com I como nó e subárvores vazias
        Caso contrário
            Inserir I na subárvore à direita

Note the following: this algorithm is recursive and the base case is when the tree is empty. In this case, inserting means building the tree and placing the item as node value. The rest is based on comparison. When you insert into a non-empty tree you ask: is the node value greater than the given item? If yes, you want to put this on the left.

Put on the left then you have two cases: the tree on the left is empty, so you use the base case, or else the tree on the left is not empty and you use recursion and have the tree on the left.

Hence analogous thinking for another case: if the node is less than or equal to the value of the item then you do it right.

Now that you know the algorithm, let’s see how this can be done oriented to Java objects with an integer tree (in C# you could make a generic tree of things as long as they are comparable, I don’t know if Java allows this). Basically the tree should have the node and subtrees on the right and left. These are the attributes of its type.

Regarding the methods we only need for this the method of inserting items and a constructor. The constructor will take care of not having to do the first check of the algorithm: the only way to build a binary tree is to give an element to be placed in the node. That way it’ll never be empty. The constructor will already set the references to the subtrees as null indicating that they are empty to be able to check the algorithm.

In the end it’ll be like this:

class ArvoreBinariaInteiros
{
    private int valorNo;
    private ArvoreBinariaInteiros subarvoreEsquerda;
    private ArvoreBinariaInteiros subarvoreDireita;

    public ArvoreBinariaInteiros(int valorNo)
    {
        this.valorNo = valorNo;
        this.subarvoreEsquerda = null;
        this.subarvoreDireita = null;
    }

    public void InserirItem(int item)
    {
         int valorNoAtual = valorNo;
         if ( item < valorNoAtual )
         {
             if (subarvoreEsquerda == null) 
             {
                 subarvoreEsquerda = new ArvoreBinariaInteiros(item);
             }
             else
             {
                 subarvoreEsquerda.InserirItem(item);
             }
         }
         else
         {
             if (subarvoreDireita == null)
             {
                 subarvoreDireita = new ArvoreBinariaInteiros(item);
             }
             else
             {
                 subarvoreDireita.InserirItem(item);
             }
         }
    }
}