Estrutura de dados Java tree? [fechado]

public class Tree<T> {
    private Node<T> root;

    public Tree(T rootData) {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }

    public static class Node<T> {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }
}

É uma estrutura de árvore básica que pode ser usada para String ou qualquer outro objecto. É bastante fácil implementar árvores simples para fazer o que você precisa.

Tudo o que você precisa adicionar São métodos para adicionar, remover, atravessar e construtores. O Node é o bloco básico de construção do Tree.

Mais uma estrutura de árvore:

public class TreeNode<T> implements Iterable<TreeNode<T>> {

    T data;
    TreeNode<T> parent;
    List<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<TreeNode<T>>();
    }

    public TreeNode<T> addChild(T child) {
        TreeNode<T> childNode = new TreeNode<T>(child);
        childNode.parent = this;
        this.children.add(childNode);
        return childNode;
    }

    // other features ...

}

Utilização da amostra:

TreeNode<String> root = new TreeNode<String>("root");
{
    TreeNode<String> node0 = root.addChild("node0");
    TreeNode<String> node1 = root.addChild("node1");
    TreeNode<String> node2 = root.addChild("node2");
    {
        TreeNode<String> node20 = node2.addChild(null);
        TreeNode<String> node21 = node2.addChild("node21");
        {
            TreeNode<String> node210 = node20.addChild("node210");
        }
    }
}

Bónus
Ver árvore completa com:

Iterator
• à procura
• Java / C#

Https://github.com/gt4dev/yet-another-tree-structure

Note que a partir do Java 9 Você pode desejar não usar estas classes porque elas não estarão presentes no compacto profiles ' .

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;

/**
  * @author [email protected] (Yohann Coppel)
  * 
  * @param <T>
  *          Object's type in the tree.
*/
public class Tree<T> {

  private T head;

  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();

  private Tree<T> parent = null;

  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();

  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }

  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }

  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }

  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }

  public T getHead() {
    return head;
  }

  public Tree<T> getTree(T element) {
    return locate.get(element);
  }

  public Tree<T> getParent() {
    return parent;
  }

  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }

  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }

  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }

  @Override
  public String toString() {
    return printTree(0);
  }

  private static final int indent = 2;

  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}

EU escrevi uma pequena biblioteca que lida com árvores genéricas. É muito mais leve do que o baloiço. Também tenho um projecto maven para ele.

public class Tree {
    private List<Tree> leaves = new LinkedList<Tree>();
    private Tree parent = null;
    private String data;

    public Tree(String data, Tree parent) {
        this.data = data;
        this.parent = parent;
    }
}

Obviamente você pode adicionar métodos utilitários para adicionar / remover crianças.

Você deve começar por definir o que é uma árvore (para o domínio), isto é melhor feito definindo a interface primeiro. Nem todas as estruturas das árvores são modificáveis, sendo capaz de adicionar e remover os nós devem ser uma funcionalidade opcional, por isso fazemos uma interface extra para isso.

Não há necessidade de criar objetos de nó que detenham os valores, na verdade eu vejo isso como uma falha de projeto principal e acima na maioria das implementações de árvores. Se você olhar para Swing, o TreeModel está livre de classes de nós (apenas DefaultTreeModel faz uso de TreeNode), pois eles não são realmente necessários.

public interface Tree <N extends Serializable> extends Serializable {
    public List<N> getRoots ();
    public N getParent (N node);
    public List<N> getChildren (N node);
}

public interface MutableTree <N extends Serializable> extends Tree<N> {
    public boolean add (N parent, N node);
    public boolean remove (N node, boolean cascade);
}

Dadas estas interfaces, o código que usa árvores não tem de se importar muito com a forma como a árvore é implementada. Isto permite que você use implementações genéricas assim como especializadas, onde você realiza a árvore delegando funções para outra API.
exemplo: estrutura da árvore de Ficheiros.

public class MappedTreeStructure<N extends Serializable> implements MutableTree<N> {

    public static void main(String[] args) {

        MutableTree<String> tree = new MappedTreeStructure<String>();
        tree.add("A", "B");
        tree.add("A", "C");
        tree.add("C", "D");
        tree.add("E", "A");
        System.out.println(tree);
    }

    private final Map<N, N> nodeParent = new HashMap<N, N>();
    private final LinkedHashSet<N> nodeList = new LinkedHashSet<N>();

    private void checkNotNull(N node, String parameterName) {
        if (node == null)
            throw new IllegalArgumentException(parameterName + " must not be null");
    }

    @Override
    public boolean add(N parent, N node) {
        checkNotNull(parent, "parent");
        checkNotNull(node, "node");

        // check for cycles
        N current = parent;
        do {
            if (node.equals(current)) {
                throw new IllegalArgumentException(" node must not be the same or an ancestor of the parent");
            }
        } while ((current = getParent(current)) != null);

        boolean added = nodeList.add(node);
        nodeList.add(parent);
        nodeParent.put(node, parent);
        return added;
    }

    @Override
    public boolean remove(N node, boolean cascade) {
        checkNotNull(node, "node");

        if (!nodeList.contains(node)) {
            return false;
        }
        if (cascade) {
            for (N child : getChildren(node)) {
                remove(child, true);
            }
        } else {
            for (N child : getChildren(node)) {
                nodeParent.remove(child);
            }
        }
        nodeList.remove(node);
        return true;
    }

    @Override
    public List<N> getRoots() {
        return getChildren(null);
    }

    @Override
    public N getParent(N node) {
        checkNotNull(node, "node");
        return nodeParent.get(node);
    }

    @Override
    public List<N> getChildren(N node) {
        List<N> children = new LinkedList<N>();
        for (N n : nodeList) {
            N parent = nodeParent.get(n);
            if (node == null && parent == null) {
                children.add(n);
            } else if (node != null && parent != null && parent.equals(node)) {
                children.add(n);
            }
        }
        return children;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        dumpNodeStructure(builder, null, "- ");
        return builder.toString();
    }

    private void dumpNodeStructure(StringBuilder builder, N node, String prefix) {
        if (node != null) {
            builder.append(prefix);
            builder.append(node.toString());
            builder.append('\n');
            prefix = "    " + prefix;
        }
        for (N child : getChildren(node)) {
            dumpNodeStructure(builder, child, prefix);
        }
    }
}

Você pode usar qualquer API XML do Java como documento e Node..as o XML é uma estrutura em árvore com cadeias de caracteres

Nenhuma resposta menciona código de trabalho demasiado simplificado, por isso aqui está:

public class TreeNodeArray<T> {
    public T value;
    public final  java.util.List<TreeNodeArray<T>> kids =  new java.util.ArrayList<TreeNodeArray<T>>();
}

Há um par de estruturas de dados de árvore em Java, tais como DefaultMutableTreeNode em JDK Swing, árvore em pacote parser Stanford, e outros códigos de brinquedos. Mas nenhuma delas é suficiente, ainda que pequena, para fins gerais.

Java-tree O projeto tenta fornecer outra estrutura de dados de árvore de propósito geral em Java. A diferença entre isto e outros é

Totalmente livre. Você pode usá-lo em qualquer lugar (exceto em seu dever de casa :p)
• pequeno mas general o suficiente. Eu coloquei tudo da estrutura de dados em um arquivo de classe, então seria fácil copiar/colar.
Não são apenas brinquedos. Estou ciente de dezenas de códigos Java tree que só podem lidar com árvores binárias ou operações limitadas. Este TreeNode é muito mais do que isso. Ele fornece diferentes maneiras de visitar nós, tais como pré-ordem, postorder, largura, folhas, caminho para raiz, etc. Além disso, também estão previstos iteradores para a suficiência.
• mais utils serão adicionados. Estou disposto a adicione mais operações para tornar este projeto abrangente, especialmente se você enviar um pedido através do github.

Nas mesmas linhas que a resposta do Gareth, confira DefaultMutableTreeNode. Não é genérico, mas parece encaixar na conta. Apesar de estar no javax.pacote swing, ele não depende de qualquer AWT ou classes Swing. Na verdade, o código fonte realmente tem o comentário // ISSUE: this class depends on nothing in AWT -- move to java.util?

Deve-se dizer ainda que a razão pela qual uma árvore não está lá como, digamos, um Pair (sobre o qual o mesmo poderia ser dito), é porque você deve estar encapsulando seus dados na classe usando-o, e a implementação mais simples parece:

/***
/* Within the class that's using a binary tree for any reason. You could 
/* generalize with generics IFF the parent class needs different value types.
 */
private class Node {
  public String value;
  public Node[] nodes; // Or an Iterable<Node> nodes;
}

Se quisesses um árvore binária é muitas vezes mais fácil de usar com campos nomeados:

private class Node { // Using package visibility is an option
  String value;
  Node left;
  Node right;
}

private class Node {
  String value;
  Map<char, Node> nodes;
}

Para ser capaz de obter todos os filhos (algum tipo de lista ou matriz de cadeias de caracteres) dado um texto de entrada que representa um determinado nó

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class kidsOfMatchTheseDays {
 static private class Node {
   String value;
   Node[] nodes;
 }

 // Pre-order; you didn't specify.
 static public List<String> list(Node node, String find) {
   return list(node, find, new ArrayList<String>(), false);
 }

 static private ArrayList<String> list(
     Node node,
     String find,
     ArrayList<String> list,
     boolean add) {
   if (node == null) {
     return list;
   }
   if (node.value.equals(find)) {
     add = true;
   }
   if (add) {
     list.add(node.value);
   }
   if (node.nodes != null) {
     for (Node child: node.nodes) {
       list(child, find, list, add);
     }
   }
   return list;
 }

 public static final void main(String... args) {
   // Usually never have to do setup like this, so excuse the style
   // And it could be cleaner by adding a constructor like:
   //     Node(String val, Node... children) {
   //         value = val;
   //         nodes = children;
   //     }
   Node tree = new Node();
   tree.value = "root";
   Node[] n = {new Node(), new Node()};
   tree.nodes = n;
   tree.nodes[0].value = "leftish";
   tree.nodes[1].value = "rightish-leafy";
   Node[] nn = {new Node()};
   tree.nodes[0].nodes = nn;
   tree.nodes[0].nodes[0].value = "off-leftish-leaf";
   // Enough setup
   System.out.println(Arrays.toString(list(tree, args[0]).toArray()));
 }
}

Isto faz-te usar como:

$ java kidsOfMatchTheseDays leftish
[leftish, off-leftish-leaf]
$ java kidsOfMatchTheseDays root
[root, leftish, off-leftish-leaf, rightish-leafy]
$ java kidsOfMatchTheseDays rightish-leafy
[rightish-leafy]
$ java kidsOfMatchTheseDays a
[]

Uma vez que a pergunta pede uma estrutura de dados disponível, uma árvore pode ser construída a partir de listas ou arrays:

Object[] tree = new Object[2];
tree[0] = "Hello";
{
  Object[] subtree = new Object[2];
  subtree[0] = "Goodbye";
  subtree[1] = "";
  tree[1] = subtree;
}

instanceof pode ser usado para determinar se um elemento é uma sub-árvore ou um nó terminal.

public abstract class Node {
  List<Node> children;

  public List<Node> getChidren() {
    if (children == null) {
      children = new ArrayList<>();
    }
    return chidren;
  }
}

Tão simples quanto possível e muito fácil de usar. Para usá-lo, estenda-o:

public class MenuItem extends Node {
  String label;
  String href;
  ...
}

Por exemplo:

import java.util.ArrayList;
import java.util.List;



/**
 * 
 * @author X2
 *
 * @param <T>
 */
public class HisTree<T> 
{
    private Node<T> root;

    public HisTree(T rootData) 
    {
        root = new Node<T>();
        root.setData(rootData);
        root.setChildren(new ArrayList<Node<T>>());
    }

}

class Node<T> 
{

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getParent() {
        return parent;
    }
    public void setParent(Node<T> parent) {
        this.parent = parent;
    }
    public List<Node<T>> getChildren() {
        return children;
    }
    public void setChildren(List<Node<T>> children) {
        this.children = children;
    }
}

Pode usar a classe hashtree incluída no Apache Jameter que faz parte do projecto Jacarta.

A classe HashTree está incluída no package org.Apache.amorfo.coleccao. Embora este pacote não seja lançado fora do projeto Jameter, você pode obtê-lo facilmente:

1) Descarregue o JMeter sources .

2) crie um novo pacote.

3) Copy on it / src/amorphan/org/apache/amorphan/ collections/. Todos os ficheiros excepto dados.java

4) copiar também /src/jorphan/org/apache/jorphan/util/JOrphanUtils.java

5) a HashTree está pronta a usar.

Verifique por favor o código abaixo, onde usei estruturas de dados em árvore, sem usar classes de recolha. O código pode ter bugs/melhorias, mas por favor use isso apenas para referência

package com.datastructure.tree;

public class BinaryTreeWithoutRecursion <T> {

    private TreeNode<T> root;


    public BinaryTreeWithoutRecursion (){
        root = null;
    }


    public void insert(T data){
        root =insert(root, data);

    }

    public TreeNode<T>  insert(TreeNode<T> node, T data ){

        TreeNode<T> newNode = new TreeNode<>();
        newNode.data = data;
        newNode.right = newNode.left = null;

        if(node==null){
            node = newNode;
            return node;
        }
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.enque(node);
        while(!queue.isEmpty()){

            TreeNode<T> temp= queue.deque();
            if(temp.left!=null){
                queue.enque(temp.left);
            }else
            {
                temp.left = newNode;

                queue =null;
                return node;
            }
            if(temp.right!=null){
                queue.enque(temp.right);
            }else
            {
                temp.right = newNode;
                queue =null;
                return node;
            }
        }
        queue=null;
        return node; 


    }

    public void inOrderPrint(TreeNode<T> root){
        if(root!=null){

            inOrderPrint(root.left);
            System.out.println(root.data);
            inOrderPrint(root.right);
        }

    }

    public void postOrderPrint(TreeNode<T> root){
        if(root!=null){

            postOrderPrint(root.left);

            postOrderPrint(root.right);
            System.out.println(root.data);
        }

    }

    public void preOrderPrint(){
        preOrderPrint(root);
    }


    public void inOrderPrint(){
        inOrderPrint(root);
    }

    public void postOrderPrint(){
        inOrderPrint(root);
    }


    public void preOrderPrint(TreeNode<T> root){
        if(root!=null){
            System.out.println(root.data);
            preOrderPrint(root.left);
            preOrderPrint(root.right);
        }

    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTreeWithoutRecursion <Integer> ls=  new BinaryTreeWithoutRecursion <>();
        ls.insert(1);
        ls.insert(2);
        ls.insert(3);
        ls.insert(4);
        ls.insert(5);
        ls.insert(6);
        ls.insert(7);
        //ls.preOrderPrint();
        ls.inOrderPrint();
        //ls.postOrderPrint();

    }

}

Não existe uma estrutura de dados específica em Java que se adapte às suas necessidades. Seus requisitos são bastante específicos e para isso você precisa projetar sua própria estrutura de dados. Olhando para os seus requisitos, qualquer um pode dizer que você precisa de algum tipo de árvore n-ary com alguma funcionalidade específica. Pode desenhar a sua estrutura de dados da seguinte forma:

1. A estrutura do nó da árvore seria como o conteúdo no nó e a lista de crianças como: class Node { String value; List crianças;}
2. Você precisa para recuperar as crianças de uma determinada seqüência de caracteres, então você pode ter 2 métodos 1: Nó searchNode(String str), vai devolver o nó que tem o mesmo valor como dado de entrada (uso de BFS para a pesquisa) 2: Lista de getChildren(String str): este método de chamada internamente o searchNode para obter o nó tendo a mesma seqüência de caracteres e, em seguida, ele irá criar a lista de todos os valores de seqüência de caracteres de crianças e de retorno.
3. também terá de inserir um texto na árvore. Você terá que escrever um método diz void insert( string parent, String value): isto irá procurar novamente o nó com valor igual ao Pai e então você poderá criar um nó com valor dado e Adicionar à lista de filhos ao Pai encontrado.

Eu sugeriria que escrevesse a estrutura do nó numa classe como o valor do nó de classe { String; List children;} e todos os outros métodos como procurar, inserir e obter crianças noutra classe de NodeUtils, para que também possa passar a raiz da árvore para efectuar a operação em árvore específica como: classe NodeUtils{ public static Node search (Node root, String value) {//perform BFS and return Node}

import com.fasterxml.jackson.annotation.JsonValue;
import com.fasterxml.jackson.databind.ObjectMapper;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created by kic on 16.07.15.
 */
public class NestedMap<K, V> {
    private final Map root = new HashMap<>();

    public NestedMap<K, V> put(K key) {
        Object nested = root.get(key);

        if (nested == null || !(nested instanceof NestedMap)) root.put(key, nested = new NestedMap<>());
        return (NestedMap<K, V>) nested;
    }

    public Map.Entry<K,V > put(K key, V value) {
        root.put(key, value);

        return (Map.Entry<K, V>) root.entrySet().stream().filter(e -> ((Map.Entry) e).getKey().equals(key)).findFirst().get();
    }

    public NestedMap<K, V> get(K key) {
        return (NestedMap<K, V>) root.get(key);
    }

    public V getValue(K key) {
        return (V) root.get(key);
    }

    @JsonValue
    public Map getRoot() {
        return root;
    }

    public static void main(String[] args) throws Exception {
        NestedMap<String, Integer> test = new NestedMap<>();
        test.put("a").put("b").put("c", 12);
        Map.Entry<String, Integer> foo = test.put("a").put("b").put("d", 12);
        test.put("b", 14);
        ObjectMapper mapper = new ObjectMapper();
        System.out.println(mapper.writeValueAsString(test));

        foo.setValue(99);
        System.out.println(mapper.writeValueAsString(test));

        System.out.println(test.get("a").get("b").getValue("d"));
    }
}

    // TestTree.java
// A simple test to see how we can build a tree and populate it
//
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;

public class TestTree extends JFrame {

  JTree tree;
  DefaultTreeModel treeModel;

  public TestTree( ) {
    super("Tree Test Example");
    setSize(400, 300);
    setDefaultCloseOperation(EXIT_ON_CLOSE);
  }

  public void init( ) {
    // Build up a bunch of TreeNodes. We use DefaultMutableTreeNode because the
    // DefaultTreeModel can use it to build a complete tree.
    DefaultMutableTreeNode root = new DefaultMutableTreeNode("Root");
    DefaultMutableTreeNode subroot = new DefaultMutableTreeNode("SubRoot");
    DefaultMutableTreeNode leaf1 = new DefaultMutableTreeNode("Leaf 1");
    DefaultMutableTreeNode leaf2 = new DefaultMutableTreeNode("Leaf 2");

    // Build our tree model starting at the root node, and then make a JTree out
    // of it.
    treeModel = new DefaultTreeModel(root);
    tree = new JTree(treeModel);

    // Build the tree up from the nodes we created.
    treeModel.insertNodeInto(subroot, root, 0);
    // Or, more succinctly:
    subroot.add(leaf1);
    root.add(leaf2);

    // Display it.
    getContentPane( ).add(tree, BorderLayout.CENTER);
  }

  public static void main(String args[]) {
    TestTree tt = new TestTree( );
    tt.init( );
    tt.setVisible(true);
  }
}

Https://github.com/RutledgePaulV/prune

Pode usar a classe TreeSet em java.util.*. Está a funcionar como uma árvore de busca binária, por isso já está ordenada. A classe TreeSet implementa interfaces iteráveis, coletáveis e ajustáveis. Podes atravessar a árvore com o iterador como um conjunto.

TreeSet<String> treeSet = new TreeSet<String>();
Iterator<String> it  = treeSet.Iterator();
while(it.hasNext()){
...
}

Pode verificar, Java Doc e alguns outros.

Eu escrevi uma pequena classe "TreeMap" baseada em "HashMap" que suporta adicionar caminhos:

import java.util.HashMap;
import java.util.LinkedList;

public class TreeMap<T> extends LinkedHashMap<T, TreeMap<T>> {

    public void put(T[] path) {
        LinkedList<T> list = new LinkedList<>();
        for (T key : path) {
            list.add(key);
        }
        return put(list);
    }

    public void put(LinkedList<T> path) {
        if (path.isEmpty()) {
            return;
        }
        T key = path.removeFirst();
        TreeMap<T> val = get(key);
        if (val == null) {
            val = new TreeMap<>();
            put(key, val);
        }
        val.put(path);
    }

}

Ele pode ser usado para armazenar uma árvore de coisas do tipo " T " (genérico), mas não (ainda) suporta armazenar dados extras em seus nós. Se tiver um ficheiro como este:

root, child 1
root, child 1, child 1a
root, child 1, child 1b
root, child 2
root, child 3, child 3a

TreeMap<String> root = new TreeMap<>();
Scanner scanner = new Scanner(new File("input.txt"));
while (scanner.hasNextLine()) {
  root.put(scanner.nextLine().split(", "));
}

Aplicação de árvore personalizada da árvore sem usar a estrutura de colecção. Contém diferentes operações fundamentais necessárias na implementação de árvores.

class Node {

    int data;
    Node left;
    Node right;

    public Node(int ddata, Node left, Node right) {
        this.data = ddata;
        this.left = null;
        this.right = null;      
    }

    public void displayNode(Node n) {
        System.out.print(n.data + " "); 
    }

}

class BinaryTree {

    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public void insertLeft(int parent, int leftvalue ) {
        Node n = find(root, parent);
        Node leftchild = new Node(leftvalue, null, null);
        n.left = leftchild;
    }

    public void insertRight(int parent, int rightvalue) {
        Node n = find(root, parent);
        Node rightchild = new Node(rightvalue, null, null);
        n.right = rightchild;
    }

    public void insertRoot(int data) {
        root = new Node(data, null, null);
    }

    public Node getRoot() {
        return root;
    }

    public Node find(Node n, int key) {     
        Node result = null;

        if (n == null)
            return null;

        if (n.data == key)
            return n;

        if (n.left != null)
            result = find(n.left, key);

        if (result == null)
            result = find(n.right, key);

        return result;
    } 

    public int getheight(Node root){
        if (root == null)
            return 0;

        return Math.max(getheight(root.left), getheight(root.right)) + 1; 
    }

    public void printTree(Node n) {     
        if (n == null)
            return;

        printTree(n.left);
        n.displayNode(n);
        printTree(n.right);             
    }

}