二叉树的递归遍历和非递归遍历（附详细例子）

                                     二叉树的递归遍历和非递归遍历（附详细例子）

        二叉树的遍历主要有递归实现和非递归实现，递归实现比较好理解，非递归实现主要是利用了栈的思想，后进先出，本文实现二叉树的非递归遍历主要是用了LinkedList可以当做栈使用的功能。具体例子如下：

package ; 

import ;
 
public class BinaryTree
{
    private TreeNode root;// 根节点

    public BinaryTree()
    {
    }
    public BinaryTree(TreeNode root)
    {
         = root;
    }
    public TreeNode getRoot()
    {
        return root;
    }
    public void setRoot(TreeNode root)
    {
         = root;
    }

    /**
     * 节点类
     */
    private static class TreeNode
    {
        private String data = null;// 数据部分
        private TreeNode left;// 左节点的引用
        private TreeNode right;// 右节点的引用
        public TreeNode(String data, TreeNode left, TreeNode right)//节点的构造函数，测试函数中创建节点就是用了它
        {
             = data;
             = left;
             = right;
        }     
        public String getData()//节点类的get和set方法
        {
            return data;
        }
        public void setData(String data)
        {
             = data;
        }
        public TreeNode getLeft()
        {
            return left;
        }
        public void setLeft(TreeNode left)
        {
             = left;
        }
        public TreeNode getRight()
        {
            return right;
        }
        public void setRight(TreeNode right)
        {
             = right;
        }
    }
 
    /**
     *  递归 前续遍历
     */
    public void preOrder(TreeNode node)
    {
        if (node != null)
        {
            (()+"  ");
            preOrder(());
            preOrder(());
        }
    }

    /**
     *  递归 中续遍历
     */
    public void inOrder(TreeNode node)
    {
        if (node != null)
        {
        	inOrder(());
        	(()+"  ");
        	inOrder(());
        }
    }

    /**
     *  递归 后续遍历
     */
    public void postOrder(TreeNode node)
    {
        if (node != null)
        {
        	postOrder(());
        	postOrder(());
        	 (()+"  ");
        }
    }
    
    /**
     *  非递归 前续遍历
     */
    public void preOrderNoRecursion() 
    { 
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); 
        (root); 
        TreeNode current = null; 
        while (!()) 
        { 
            current = (); 
            (+"  "); 
            if (() != null) 
                (()); 
            if (() != null) 
                (()); 
        } 
        (); 
    } 
    
    /**
     *  非递归 中续遍历
     */
    public void inorderNoRecursion() 
    { 
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); 
        TreeNode current = root; 
        while (current != null || !()) 
        { 
            while(current != null) 
            { 
                (current); 
                current = (); 
            } 
            if (!()) 
            { 
                current = (); 
                (+"  "); 
                current = (); 
            } 
        } 
        (); 
    } 
    
    /**
     *  非递归 后续遍历
     */
    public void postorderNoRecursion() 
    { 
        TreeNode rNode = null; 
        TreeNode current = root; 
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); 
        while(current != null || !()) 
        { 
            while(current != null) 
            { 
                (current); 
                current = (); 
            } 
            current = (); 
            while (current != null && (() == null ||() == rNode)) 
            { 
                (+"  "); 
                rNode = current; 
                if (())
                { 
                    (); 
                    return; 
                } 
                current = (); 
            } 
            (current); 
            current = (); 
        }          
    } 
    
    public static void main(String[] args)
    {
        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);// 创建根节点

        BinaryTree bt = new BinaryTree(root);
        (" 递归 前序遍历------->");
        (());
        (" 非递归 前序遍历------->");
        ();
        (" 递归 中序遍历------->");
        (());
        (" 非递归 中序遍历------->");
        ();
        (" 递归 后序遍历------->");
        (());
        (" 非递归 后序遍历------->");
        ();
        
    }
}
    

递归 前序遍历------->A  B  D  C  E   非递归 前序遍历------->A   B  D  C  E 
递归 中序遍历------->B  D  A  E  C   非递归 中序遍历------->B  D  A  E  C  
递归 后序遍历------->D  B  E  C  A   非递归 后序遍历------->D  B  E  C  A