树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。

它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；

• 没有父节点的节点称为根节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树；

• 树里面没有环路(cycle)

为什么需要树

因为它结合了另外两种数据结构的优点：一种是有序数组，另一种是链表。在树中查找数据项的速度和在有序数组中查找一样快， 并且插入数据项和删除数据项的速度也和链表一样。

都有哪些树

树的种类有很多，我们接触到的树有二叉树、平衡二叉树、二叉查找树、B树、B+树、哈夫曼树、B*树、红黑树和trie树等。

树的实现

树是一种递归结构，表示方式一般有孩子表示法和孩子兄弟表示法两种。树实现方式有很多种、有可以由广义表的递归实现，也可以有二叉树实现，其中最常见的是将树用孩子兄弟表示法转化成二叉树来实现。

实现代码：

publicclass treeNode<T> {
  public T t;
  private treeNode<T> parent;
   
  public List<treeNode<T>> nodelist;
   
  public treeNode(T stype){
    t   = stype;
    parent = null;
    nodelist = new ArrayList<treeNode<T>>();
  }
 
  public treeNode<T> getParent() {
    return parent;
  }  
}


publicclass tree<T> {
   
  public treeNode<T> root;
   
  public tree(){}
     
  public void addNode(treeNode<T> node, T newNode){
    //增加根节点
    if(null == node){
      if(null == root){
        root = new treeNode(newNode);
      }
    }else{
        treeNode<T> temp = new treeNode(newNode);
        node.nodelist.add(temp);
    }
  }
   
  /*  查找newNode这个节点 */
  public treeNode<T> search(treeNode<T> input, T newNode){
   
    treeNode<T> temp = null;
     
    if(input.t.equals(newNode)){
      return input;
    }
     
    for(int i = 0; i < input.nodelist.size(); i++){
       
      temp = search(input.nodelist.get(i), newNode);
       
      if(null != temp){
        break;
      }  
    }
     
    return temp;
  }
   
  public treeNode<T> getNode(T newNode){
    return search(root, newNode);
  }
   
  public void showNode(treeNode<T> node){
    if(null != node){
      //循环遍历node的节点
      System.out.println(node.t.toString());
       
      for(int i = 0; i < node.nodelist.size(); i++){
        showNode(node.nodelist.get(i));
      }      
    }
  }
}


public static void main(String[] args) {

    tree<String> tree = new tree();
    tree.addNode(null, "string");
    tree.addNode(tree.getNode("string"), "hello");
    tree.addNode(tree.getNode("string"), "world");
    tree.addNode(tree.getNode("hello"), "sinny");
    tree.addNode(tree.getNode("hello"), "fredric");
    tree.addNode(tree.getNode("world"), "Hi");
    tree.addNode(tree.getNode("world"), "York");
    tree.showNode(tree.root);
    System.out.println("end of the test");
  }