package com.huangxin.test;

import java.util.Stack;

public class TreeOrder {

    public static void main(String[] args) {
        //創(chuàng)建一個二叉樹
        TreeNode node1=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        TreeNode node7=new TreeNode(7);
        TreeNode node8=new TreeNode(8);
        TreeNode node9=new TreeNode(9);
        TreeNode node10=new TreeNode(10);
        TreeNode node11=new TreeNode(11);
        
        node1.left=node2;
        node1.right=node3;
        node2.right=node6;
        node2.left=node5;
        node5.left=node9;
        node5.right=node10;
        node3.left=node7;
        node3.right=node8;
        node7.left=node11;
        
        
        System.out.print("遞歸前序遍歷:");
        preOrder(node1);
        System.out.println(" ");
        System.out.print("非遞歸前序遍歷:");
        preOrderNoRec(node1);
        System.out.println(" ");
        
        System.out.print("遞歸中序遍歷：");
        inOrder(node1);
        System.out.println(" ");
        System.out.print("非遞歸中序遍歷：");
        inOrderNoRec(node1);
        System.out.println(" ");
        
        
        System.out.print("遞歸后序遍歷：");
        posOrder(node1);
        System.out.println(" ");
        System.out.print("非遞歸后序遍歷：");
        posOrderNoRec(node1);
        System.out.println(" ");
    }
    //前中后的遞歸遍歷
    //遞歸前序遍歷
    public static void preOrder(TreeNode treeNode) {
        if(treeNode==null) {
            return;
        }
        System.out.print(treeNode.val+"  ");
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }
    
    //遞歸中序遍歷
    public static void inOrder(TreeNode treeNode) {
        if(treeNode==null) {
            return;
        }
        inOrder(treeNode.left);
        System.out.print(treeNode.val+"  ");
        inOrder(treeNode.right);
    }
    
    
    
    //遞歸后序遍歷
    public static void posOrder(TreeNode treeNode) {
        if(treeNode==null) {
            return;
        }
        posOrder(treeNode.left);
        posOrder(treeNode.right);
        System.out.print(treeNode.val+"  ");
    }
    
    //非遞歸的前序遍歷
    public static void preOrderNoRec(TreeNode treeNode){
        if(treeNode==null) {
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        stack.push(treeNode);
        while(!stack.isEmpty()) {
            TreeNode node=stack.pop();
            System.out.print(node.val+"  ");
            if(node.right!=null) {
                stack.push(node.right);
            }
            if(node.left!=null) {
                stack.push(node.left);
            }
        }
        
    }
    
    //中序的非遞歸遍歷
    public static void inOrderNoRec(TreeNode treeNode) {
        if(treeNode==null) {
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        while(!stack.isEmpty()||treeNode!=null) {
            while(treeNode!=null) {
                stack.push(treeNode);
                //添加所有的左節(jié)點
                treeNode=treeNode.left;
            }
            if(!stack.isEmpty()) {
                TreeNode tempNode=stack.pop();
                System.out.print(tempNode.val+"  ");
                treeNode=tempNode.right;
            }
        }
    }
    
    //后序遍歷非遞歸的方法
    public static void posOrderNoRec(TreeNode treeNode) {
        //利用雙棧的方法
        if(treeNode==null) {
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        Stack<TreeNode> stack1=new Stack<>();
        stack.push(treeNode);
        while(!stack.isEmpty()){
            treeNode=stack.pop();
            //將跟節(jié)點添加到Stack2
            stack1.push(treeNode);
            //添加到左節(jié)點添加到stack
            if(treeNode.left!=null) {
                stack.push(treeNode.left);
            }
            //添加到右子節(jié)點到stack
            if(treeNode.right!=null) {
                stack.push(treeNode.right);
            }
            
        }
        //遍歷輸出
        while(!stack1.isEmpty()) {
            System.out.print(stack1.pop().val+"  ");
        }
    }

}

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val=val;
    }
}

參考：https://blog.csdn.net/davidddl/article/details/75667092
https://blog.csdn.net/weixin_42130471/article/details/82904161
https://blog.csdn.net/u011514810/article/details/75907170?utm_source=blogxgwz0