binarytree.java

Java是最优秀的高级编程语言之一,二叉树是一种重要的数据结构.

public class BinaryTree 
{
    BinaryNode root;
	
	public BinaryTree()
	{
		root = null;
	}
	public BinaryTree(BinaryNode r)
	{
		root = r;
	}
	
	public boolean isEmpty()
	{
		return root == null;
	}
	
	public void visit(BinaryNode x)
	{
		x.print();
	}
	public void preorder()
	{
		Stack s = new Stack();
		BinaryNode p = root;
		
		for(;;)
		{
			while(p!= null)
			{
				visit(p);
			    s.push(p);
			    p = p.left;
		    }
		    if (!s.isEmpty())
            {  
               p = s.pop().element;    
               p = p.right; 
            }
         else return;
		}
	}
	public void inorder()
	{
		Stack s = new Stack();
		BinaryNode p = root;
		
		for(;;)
		{
			while(p!= null)
			{
			    s.push(p);
			    p = p.left;
		    }
		    if(!s.isEmpty())
		    {
		    	p = s.pop().element;
		    	visit(p);
		    	p = p.right;
		    }
		    else return;
		}
	}
	public void postorder()
	{
		Stack s = new Stack();
		BinaryNode p = root;
		ListNode t;
		
		for(;;)
		{
			while(p!= null)
			{
				s.push(p,1);
				p = p.left;
			}
			t = s.pop(); p = t.element;
			while(t.tag==2||p.right==null)
			{
				visit(p);
				if(!s.isEmpty())t = s.pop();
				else return;
				p = t.element;
			}
			if(t.tag == 1)s.push(p,2);
			p = p.right;
		}
	}
}