二叉树的java实现

树是一种重要的非线性数据结构，二叉树又是每个节点最多只有两个字节点的树。每一层的节点从左至右顺序排列叫做有序二叉树
二叉树主要用途用于排序和查找。

以下是java实现的，给定一个无序的数字集合，将他们生成二叉树，排序，并且可以查询某个数字是否在树中。

package com.tree;

import java.util.ArrayList;
import java.util.Date;
import java.util.LinkedList;
import java.util.List;

/**
 * yuyong 2012-11-2
 */
public class BinaryTree {
    public LinkedList list=new LinkedList();
    public TreeNode root;
    public BinaryTree(Double[] objs){
        for(Double obj:objs){
            if(root==null){
                root=new TreeNode(obj);
            }else
                add(obj,root);
        }
        sort(root);
    }

    private void add(Double obj,TreeNode node){
        int result=node.value.compareTo(obj);
        if(result>0){
           if(node.left==null)
               node.left=new TreeNode(obj);
            else
               add(obj,node.left);
        }else if(result==0){
            node.count++;
        }else if(result <0){
            if(node.right==null)
                node.right=new TreeNode(obj);
            else
                add(obj,node.right);
        }
    }

    private void sort(TreeNode node){
        if(node.left!=null){
            sort(node.left);
        }
        for(int i=1;i<=node.count;i++){
            list.addLast(node.value);
        }
        if(node.right!=null){
            sort(node.right);
        }
    }

     public boolean search(TreeNode node,double value){
        if(node.value==value)
            return true;
        else{
            if(node.value>value)
                if(node.left!=null)
                    search(node.left,value);
            else{
                    if(node.right!=null)
                        search(node.right,value);
                }
        }
        return false;

    }

    class TreeNode{
        public Double value;
        public int count=1;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(Double value){
            if(this.value==value)
                count++;
            this.value=value;
        }
    }

    public static void main(String args[]){
        Double[] v=new Double[10];
        double j = 0;
        for(int i=0;i<10;i++){
            v[i]=Math.random()*10.0;
            if(i==0)
                j=v[i];
        }
        BinaryTree tree=new BinaryTree(v);
        System.out.println(tree.list);
        System.out.println(tree.search(tree.root,j));
        System.out.println(tree.search(tree.root,12));
   }

}

输出 [0.46790557311640946, 1.8071286450071067, 3.3232331287984884, 3.8719511345032886, 4.324591780113119, 5.4900862924918705, 5.5018668278276035, 5.834691623616115, 6.31628258744162, 7.180319020755257]
true
false

add方法是添加节点到树中，取数字集合的第一个数字为整棵树的跟节点。然后依次取后面的数字，从根节点开始进行比较，如果大于节点，就到节点的右子树中进行比较，如果小于根节点，就到节点的左子树中进行比较，直到找不到节点的时候，就在相应位置生成一个新的节点。如果找到和他相同的值的节点，就此节点记录相同值的次数。这样比数字集合第一个数字小的数字都在根节点的左子树中，比他大的数字都在根节点的右子树中。

sort方法是从先取出左子树的节点，取出中间节点，取出右子树节点，如此方式从根节点开始，这样最后得到的是升序的数字集合

search方法是将要查询的数字和中间节点进行比较。比中间节点值大就到右子树中如此查询，反之就到左子树中如此查询。