/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package treeapp;

/**
 *
 * @author pablo
 */
public class Tree {

    private Node root;                           // o único campo de dado em Tree

    public Node find(int key) {                  // encontra no com uma dada chave
        // (assume arvore nao vazia)
        Node current = root;                     // começa na raiz
        while (current.iData != key) {             // enquanto nao coincide
            if (key < current.iData) {            // ir para a esquerda?
                current = current.leftChild;
            } else {
                current = current.rightChild;    // ou para a direita?
            }
            if (current == null) {                // se nao ha filho
                return null;                        // nao o encontrou
            }

        }
        return current;                             // encontrou-o
    }

    public void insert(int id, double dd) {
        Node newNode = new Node();                         // cria novo nó
        newNode.iData = id;                                // insere dado
        newNode.dData = dd;

        if (root == null) {                                // sem nó na raiz
            root = newNode;
        } else {                                             // raiz ocupada
            Node current = root;                           // começa na raiz
            Node parent;
            while (true) {                                   // (sai internamente)
                parent = current;
                if (id < current.iData) {                    // vai p/ esquerda?
                    current = current.leftChild;
                    if (current == null) {                   // se fim da linha,
                        parent.leftChild = newNode;        // insere a esquerda
                        return;
                    }
                } // fim do if de ir p/ esquerda;
                else {                                      // ou para a direita?
                    current = current.rightChild;
                    if (current == null) {                 // se fim da linha
                        parent.rightChild = newNode;       // inserir a direita
                        return;
                    }
                } // fim do else ir para a direita
            } // fim do while
        } // fim do else não raiz
    } // fim de insert()

    public void delete(int id) {
    }

    private void inOrder(Node localRoot) {
        if (localRoot != null) {
            inOrder(localRoot.leftChild);

            System.out.println(localRoot.iData + " ");
            inOrder(localRoot.rightChild);
        }
    }

    private void preOrder(Node localRoot) {
        if (localRoot != null) {
            System.out.println(localRoot.iData + " ");

            preOrder(localRoot.leftChild);
            preOrder(localRoot.rightChild);
        }
    }

    public void posOrder(Node localRoot) {
        posOrder(localRoot.leftChild);
        posOrder(localRoot.rightChild);

        System.out.println(localRoot.iData + " ");
    }

    public Node minimum() {                      // retorna nó com chave de valor mínimo
        Node current, last = null;
        current = root;                         // começa na raiz

        while (current != null) {                 // até o fundo,
            last = current;                     // lembra nó
            current = current.leftChild;        // vai para o filho a esquerda
        }
        return last;
    }

    public Node maximum() {
        Node current, last = null;
        current = root;

        while (current != null) {
            last = current;
            current = current.rightChild;
        }
        return last;
    }

// retorna nó com o próximo valor mais alto depois de delNode
// vai p/ filho à direita, então p/ descendentes dele à esquerda
    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightChild;          // vai p/ filho à direita

        while (current != null) {                   // até não mais
            successorParent = successor;            // filhos à esquerda,
            successor = current;
            current = current.leftChild;            // vai para filho à esquerda
        }

        if (successor != delNode.rightChild) {                      // se sucessor não é
            successorParent.leftChild = successor.rightChild;       // o filho à direita,
            successor.rightChild = delNode.rightChild;              // faz conexões
        }
        return successor;
    }
}