二叉树的遍历算法Java实现

学习并总结了二叉树的递归和非递归的遍历方式~

http://blog.csdn.net/sheepmu/article/details/28941285
http://blog.csdn.net/clam_clam/article/details/6845399
学习并总结了这两位博主的文章，很赞，谢谢~

下面是自己边敲边学的代码。

package tree;
import java.util.LinkedList;
public class Binaryorder {

private TreeNode root; //根节点
public Binaryorder()
    {

    }
public Binaryorder(TreeNode root)
    {
this.root=root;
    }
public TreeNode getRoot()
    {
return root;
    }
public void setRoot(TreeNode root)
    {
this.root=root;
    }

/*
 * 递归 前序遍历
 */
public void preOrder(TreeNode node)
    {
if(node!=null)
        {
            System.out.print(node.getdata()+" ");
            preOrder(node.getleft());
            preOrder(node.getright());
        }
    }
/*
 * 递归 中序遍历
 */
public void inOrder(TreeNode node)
    {
if(node!=null)
        {
            inOrder(node.getleft());
            System.out.println(node.getdata()+" ");
            inOrder(node.getright());
        }
    }
/*
 * 递归 后序遍历
 */
public void postOrder(TreeNode node)
    {
if(node!=null)
        {
            postOrder(node.getleft());
            postOrder(node.getright());
            System.out.println(node.getdata()+" ");
        }
    }

/*
 * 非递归 前序遍历
 */
public void preOrdernorec(TreeNode root)
    {
        LinkedList<TreeNode> list= new LinkedList<TreeNode>();
list.push(root);
        TreeNode cur=null;
while(!list.isEmpty())
        {
            cur=list.poll();  //!!!
            System.out.print(cur.getdata()+" ");
if(cur.getright()!=null)
list.push(cur.getright()); //!!!
if(cur.getleft()!=null)
list.push(cur.getleft()); //这里使用push就是当做栈在使用，如果换成add就不是这样的输出
        }

    }

/*
 * 非递归 中序遍历
 */
public void inordernocur(TreeNode root)
    {
        LinkedList<TreeNode> list= new LinkedList<TreeNode>();
        TreeNode cur=root;
while(cur!=null||! list.isEmpty())
        {
while(cur!=null)
            {
list.push(cur);
                cur=cur.getleft();
            }
if(!list.isEmpty())
            {
                cur=list.pop();
                System.out.println(cur.getdata()+" ");
                cur=cur.getright();
            }
        }
    }

    /*
 * 非递归 后序遍历 单栈法
 */
public void postordernocur(TreeNode root)
    {
Stack<TreeNode> stack= new Stack<TreeNode>();
        TreeNode cur=root;
        TreeNode node=root;
while(cur!=null||!stack.isEmpty())
        {
while(cur!=null)
            {
stack.push(cur);
                cur=cur.getleft();  
            }
if(stack.size()>0)
            {
                TreeNode temp=stack.peek().getright();

if(temp==null||temp==node)//注意第二个条件
                {
                    cur=stack.pop();
                    System.out.print(cur.getdata()+" ");
                    node=cur;
                    cur=null;
                }
else
                    cur=temp;

            }
        }
    }

/*
 * 双栈法
 */
public void postordernocur2(TreeNode root)
    {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<TreeNode> temp = new Stack<TreeNode>();
        TreeNode node=root;
while(node!=null||stack.size()>0)
        {
while(node!=null)
            {
                temp.push(node);
stack.push(node);
                node=node.getright();
            }
if(stack.size()>0)
            {
                node=stack.pop();
                node=node.getleft();
            }
        }
while(temp.size()>0)
        {
            node=temp.pop();
            System.out.print(node.getdata()+" ");
        }
    }

//节点类
      class TreeNode
    {
private String data=null;//数据部分
private TreeNode left;
private TreeNode right;
public TreeNode(String data,TreeNode left,TreeNode right)
        {
this.data=data;
this.left=left;
this.right=right;
        }
public String getdata()
        {
return data;
        }
public void setdata(String data)
        {
this.data=data;
        }
public TreeNode getleft()
        {
return left;
        }
public void setleft(TreeNode left)
        {
this.left=left;
        }
public TreeNode getright()
        {
return right;
        }
public void setright(TreeNode right)
        {
this.right=right;
        }
    }

//主函数
public static void main(String[] args) {

        Binaryorder b =new Binaryorder();
//构造二叉树
        TreeNode l2=new TreeNode("E",null,null);
        TreeNode r2=new TreeNode("D",null,null);
        TreeNode l1=new TreeNode("B",null,r2);
        TreeNode r1=new TreeNode("C",l2,null);
        TreeNode root=new TreeNode("A",l1,r1);

        b.postOrder(root);
        System.out.println("----");
        b.postordernocur(root);
  }
}