How to traverse a binary tree?

Question

How to traverse a binary tree?

Navigation

#1 by (7 votes)

3

I'm having difficulty adding an element to a binary tree because I do not know how to go through it ...

Tree node

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
        }
    }



}

java

asked by anonymous 01.06.2014 / 16:46

1 answer

A single script for N forms Concatenate date in PHP to insert into MySQL

score 7 · Accepted Answer

When you use 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, insert means constructing the tree and placing the item as the value of the node. The rest is based on comparison. When you enter a non-empty tree, you ask yourself: is the node value greater than the given node's value? If so, you want to put that on the left.

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

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

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

With regard to the methods we only need to do this the method of inserting items and a constructor. The constructor will take care of not having to do the first verification of the algorithm: the only way to build a binary tree will be giving an element to be placed in the node. That way it will never be empty. The constructor will already set the subtree references as null indicating that they are empty so you can check the algorithm.

At the end it will look 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);
             }
         }
    }
}