参考答案

public class Tree {
    private int data;   /* 数据节点 */
    private Tree    left;   /* 左子树 */
    private Tree    right;  /* 右子树 */
    public Tree( int data )
    {
        this.data   = data;
        this.left   = null;
        this.right  = null;
    }

    /**
     * 创建二叉树，返回根结点
     */
    public static Tree createTree( int[] input )
    {
        Tree    root    = null;
        Tree    temp    = null;
        for ( int i = 0; i < input.length; i++ )
        {
            /* 创建根节点 */
            if ( root == null )
            {
                root = temp = new Tree( input[i] );
            } else {
                /* 回到根结点 */
                temp = root;
                /* 添加节点 */
                while ( temp.data != input[i] )
                {
                    if ( input[i] <= temp.data )
                    {
                        if ( temp.left != null )
                        {
                            temp = temp.left;
                        } else {
                            temp.left = new Tree( input[i] );
                        }
                    } else {
                        if ( temp.right != null )
                        {
                            temp = temp.right;
                        } else {
                            temp.right = new Tree( input[i] );
                        }
                    }
                }
            }
        }
        return(root);
    }

    /**
     * 前序遍历
     */
    public static void preOrder( Tree tree )
    {
        if ( tree != null )
        {
            System.out.print( tree.data + “ ” );
            preOrder( tree.left );
            preOrder( tree.right );
        }
    }

    /**
     * 中序遍历
     */
    public static void midOrder( Tree tree )
    {
        if ( tree != null )
        {
            midOrder( tree.left );
            System.out.print( tree.data + “ ” );
            midOrder( tree.right );
        }
    }

    /**
     * 后序遍历
     */
    public static void posOrder( Tree tree )
    {
        if ( tree != null )
        {
            posOrder( tree.left );
            posOrder( tree.right );
            System.out.print( tree.data + “ ” );
        }
    }

    /**
     * 求二叉树的深度
     */
    public static int length( Tree tree )
    {
        int depth1;
        int depth2;
        if ( tree == null )
            return(0);
        /* 左子树的深度 */
        depth1 = length( tree.left );
        /* 右子树的深度 */
        depth2 = length( tree.right );
        if ( depth1 > depth2 )
            return(depth1 + 1);
        else
            return(depth2 + 1);
    }

    public static void main( String[] args )
    {
        int[] input = { 4, 2, 6, 1, 3, 5, 7, 8, 10 };
        Tree tree = createTree( input );
        System.out.print( “ 前序遍历 ： “ );
        preOrder( tree );
        System.out.print( “ \ n 中 序遍历 ： “ );
        midOrder( tree );
        System.out.print( “ \ n 后 序遍历 ： “ );
        posOrder( tree );
    }
}