求教 二叉树!

Question

  
   小弟 自学 对于这个书上的二叉树看得比较郁闷.......
    求教一段适合我这种入门级菜鸟的二叉树代码!     小弟感激不尽!
     希望带有注释,  别太复杂,简单点就行,那个什么层次遍历之类的就不用写了.....写了现在也看不懂.....
    
     谢谢!!~!

Answer 1

应LZ要求只写了三个遍历算法，且是递归调用。LZ懂递归的话应该很好理解。

Answer 2

先定义二叉树的节点final class BinaryNode<AnyType>
{
    public BinaryNode( )
    {
        this( null, null, null );
    }
    
    public BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
    {
        element = theElement;
        left    = lt;
        right   = rt;
    }    /**
     * Return the size of the binary tree rooted at t.
     */
    public static <AnyType> int size( BinaryNode<AnyType> t )
    {
        if( t == null )
            return 0;
        else
            return 1 + size( t.left ) + size( t.right );
    }    /**
     * Return the height of the binary tree rooted at t.
     */
    public static <AnyType> int height( BinaryNode<AnyType> t )
    {
        if( t == null )
            return -1;
        else
            return 1 + Math.max( height( t.left ), height( t.right ) );
    }    // Print tree rooted at current node using preorder traversal.
    public void printPreOrder( )
    {
        System.out.println( element );       // Node
        if( left != null )
            left.printPreOrder( );           // Left
        if( right != null )
            right.printPreOrder( );          // Right
    }
    // Print tree rooted at current node using postorder traversal.
    public void printPostOrder( )
    {
        if( left != null )
            left.printPostOrder( );          // Left
        if( right != null )
            right.printPostOrder( );         // Right
        System.out.println( element );       // Node
    }    // Print tree rooted at current node using inorder traversal.
    public void printInOrder( )
    {
        if( left != null )
            left.printInOrder( );            // Left
        System.out.println( element );       // Node
        if( right != null )
            right.printInOrder( );           // Right
    }
    /**
     * Return a reference to a node that is the root of a
     * duplicate of the binary tree rooted at the current node.
     */
    public BinaryNode<AnyType> duplicate( )
    {
        BinaryNode<AnyType> root = new BinaryNode<AnyType>( element, null, null );        if( left != null )            // If there's a left subtree
            root.left = left.duplicate( );    // Duplicate; attach
        if( right != null )          // If there's a right subtree
            root.right = right.duplicate( );  // Duplicate; attach
        return root;                      // Return resulting tree
    }
    
    public AnyType getElement( )
    {
        return element;
    }
    
    public BinaryNode<AnyType> getLeft( )
    {
        return left;
    }
    
    public BinaryNode<AnyType> getRight( )
    {
        return right;
    }
    
    public void setElement( AnyType x )
    {
        element = x;
    }
    
    public void setLeft( BinaryNode<AnyType> t )
    {
        left = t;
    }
    
    public void setRight( BinaryNode<AnyType> t )
    {
        right = t;
    }    private AnyType             element;
    private BinaryNode<AnyType> left;
    private BinaryNode<AnyType> right;
}
二叉树的遍历操作public class BinaryTree<AnyType>
{
    public BinaryTree( )
    {
        root = null;
    }    public BinaryTree( AnyType rootItem )
    {
        root = new BinaryNode<AnyType>( rootItem, null, null );
    }    public void printPreOrder( )
    {
        if( root != null )
            root.printPreOrder( );
    }    public void printInOrder( )
    {
        if( root != null )
           root.printInOrder( );
    }    public void printPostOrder( )
    {
        if( root != null )
           root.printPostOrder( );
    }    public void makeEmpty( )
    {
        root = null;
    }    public boolean isEmpty( )
    {
        return root == null;
    }
    
    /**
     * Merge routine for BinaryTree class.
     * Forms a new tree from rootItem, t1 and t2.
     * Does not allow t1 and t2 to be the same.
     * Correctly handles other aliasing conditions.
     */
    public void merge( AnyType rootItem, BinaryTree<AnyType> t1, BinaryTree<AnyType> t2 )
    {
        if( t1.root == t2.root && t1.root != null )
        {
            System.err.println( "leftTree==rightTree; merge aborted" );
            return;
        }            // Allocate new node
        root = new BinaryNode<AnyType>( rootItem, t1.root, t2.root );            // Ensure that every node is in one tree
        if( this != t1 )
            t1.root = null;
        if( this != t2 )
            t2.root = null;
    }    public int size( )
    {
        return BinaryNode.size( root );
    }    public int height( )
    {
        return BinaryNode.height( root );
    }    public BinaryNode<AnyType> getRoot( )
    {
        return root;
    }
    
    private BinaryNode<AnyType> root;    static public void main( String [ ] args )
    {
        BinaryTree<Integer> t1 = new BinaryTree<Integer>( 1 );
        BinaryTree<Integer> t3 = new BinaryTree<Integer>( 3 );
        BinaryTree<Integer> t5 = new BinaryTree<Integer>( 5 );
        BinaryTree<Integer> t7 = new BinaryTree<Integer>( 7 );
        BinaryTree<Integer> t2 = new BinaryTree<Integer>( );
        BinaryTree<Integer> t4 = new BinaryTree<Integer>( );
        BinaryTree<Integer> t6 = new BinaryTree<Integer>( );        t2.merge( 2, t1, t3 );
        t6.merge( 6, t5, t7 );
        t4.merge( 4, t2, t6 );        System.out.println( "t4 should be perfect 1-7; t2 empty" );
        System.out.println( "----------------" );
        System.out.println( "t4" );
        t4.printInOrder( );
        System.out.println( "----------------" );
        System.out.println( "t2" );
        t2.printInOrder( );
        System.out.println( "----------------" );
        System.out.println( "t4 size: " + t4.size( ) );
        System.out.println( "t4 height: " + t4.height( ) );
    }
}

Answer 3

建议LZ先把recursion看完了再看binary tree