二叉树的前序，中序，后序遍历（递归和非递归写法）_非递归后序周游

一、前序遍历

        前序遍历是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右

        前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。

        若二叉树为空则结束返回，否则：

        （1）访问根结点。

        （2）前序遍历左子树。

        （3）前序遍历右子树 。

        如图所示，前序遍历的结果为：ABDECFG

 

递归实现：

public class TreeNode {//定义二叉树节点
    TreeNode leftnode;
    TreeNode rightnode;
    String v;
    public TreeNode(String v){
        this.v=v;
    }
    //递归前序
    public void preOrder(TreeNode root){
        if(root != null){
            System.out.print(root.v);//打印根节点
            preOrder(root.leftnode);//访问左节点
            preOrder(root.rightnode);//访问右节点
        }
    }
}

测试代码，下同

public class Test {
    public static void main(String[] args) {
        TreeNode n1=new TreeNode("A");
        TreeNode n2=new TreeNode("B");
        TreeNode n3=new TreeNode("C");
        TreeNode n4=new TreeNode("D");
        TreeNode n5=new TreeNode("E");
        TreeNode n6=new TreeNode("F");
        TreeNode n7=new TreeNode("G");
        n1.leftnode=n2;
        n1.rightnode=n3;
        n2.leftnode=n4;
        n2.rightnode=n5;
        n3.leftnode=n6;
        n3.rightnode=n7;
        n1.preOrder(n1);
 
    }
}

测试结果：

非递归实现：

        根节点存入栈中打印根节点，然后访问这个根节点的左子树，左子树也是将左子树的根存入栈中打印根节点，依次往下直到左子树为空，再取出栈顶元素，栈顶元素(访问完左子树的根节点)作为新的根节点去访问右子树。

 

public class TreeNode {//定义二叉树节点
    TreeNode leftnode;
    TreeNode rightnode;
    String v;
    public TreeNode(String v){
        this.v=v;
    }
    //非递归前序
    public void preOrder(TreeNode root){
        Stack<TreeNode> stack =new Stack<>();//定义一个栈用于存放节点
        while (root!=null || !stack.isEmpty()){//判断二叉树是否遍历完
            while (root!=null){//往左走
                stack.push(root);//根节点入栈
                System.out.print(root.v);//打印根节点
                root=root.leftnode;//访问根节点的左节点
            }
            root=stack.pop();//取出根节点
            root=root.rightnode;//访问根节点的右节点
        }
    }
}

测试结果：

二、中序遍历 

        中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。可记作左跟右

        中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

        若二叉树为空则结束返回，否则：

        （1）中序遍历左子树

        （2）访问根结点

        （3）中序遍历右子树

如图所示，中序遍历的结果为：DBEAFCG

递归实现：

public class TreeNode {//定义二叉树节点
    TreeNode leftnode;
    TreeNode rightnode;
    String v;
    public TreeNode(String v){
        this.v=v;
    }
 
        //递归中序
    public void preOrder(TreeNode root){
        if(root != null){
            preOrder(root.leftnode);//访问左节点
            System.out.print(root.v);//打印根节点
            preOrder(root.rightnode);//访问右节点
        }
    }
}

 测试结果：

 非递归方式

        与前序方式基本相同，不同的是不先打印根节点，而是先访问左子树，在打印根节点，在访问右子树。

public class TreeNode {//定义二叉树节点
    TreeNode leftnode;
    TreeNode rightnode;
    String v;
    public TreeNode(String v){
        this.v=v;
    }
    //非递归中序
    public void preOrder(TreeNode root){
        Stack<TreeNode> stack =new Stack<>();//定义一个栈用于存放节点
        while (root!=null || !stack.isEmpty()){//判断二叉树是否遍历完
            while (root!=null){//往左走
                stack.push(root);//根节点入栈
                root=root.leftnode;//访问根节点的左节点
            }
            root=stack.pop();//取出根节点
            System.out.print(root.v);//打印根节点
            root=root.rightnode;//访问根节点的右节点
        }
    }
}

测试结果：

 

后序遍历

        后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。  

        后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：

若二叉树为空则结束返回，否则：

        （1）后序遍历左子树

        （2）后序遍历右子树

        （3）访问根结点

 如图所示，中序遍历的结果为：DEBFGCA\

 递归方法

public class TreeNode {//定义二叉树节点
    TreeNode leftnode;
    TreeNode rightnode;
    String v;
    public TreeNode(String v){
        this.v=v;
    }
            //递归后序
    public void preOrder(TreeNode root){
        if(root != null){
            preOrder(root.leftnode);//访问左节点
            preOrder(root.rightnode);//访问右节点
            System.out.print(root.v);//打印根节点
        }
    }
}

 测试结果：

非递归方法 

public class TreeNode {//定义二叉树节点
    TreeNode leftnode;
    TreeNode rightnode;
    String v;
    public TreeNode(String v){
        this.v=v;
    }
 
        //非递归后序
    public void preOrder(TreeNode root){
        Stack<TreeNode> stack =new Stack<>();//定义一个栈用于存放节点
        TreeNode node =root;
        TreeNode p=null;
        while (node!=null || !stack.isEmpty()){//判断二叉树是否遍历完
            while (node!=null){//往左走
                stack.push(node);//根节点入栈
                node=node.leftnode;//访问根节点的左节点
            }
            node=stack.peek();//判断栈顶元素
 
            if (node.rightnode==null || node.rightnode==p){
                node=stack.pop();//打印根节点，并出栈，将打印过的节点从栈中删除
                System.out.print(node.v);
                p=node;//记录prev，表示以当前prev为根的子树已经访问过了
                node=null;//node置null就不会再次访问以node为根节点的左右子树，这里的node既然已经打印，说明它的左右子树早已访问完毕
            }else {
                node=node.rightnode;//访问右子树
            }
 
        }
    }
}

测试结果：