Java二叉树的遍历递归和非递归(先、中、后)+层次

如图所示二叉树

• 先序遍历：FCADBEHGM 根左右
• 中序遍历：ACBDFHEMG 左根右
• 后续遍历：ABDCHMGEF 左右根
• 层次遍历：FCEADHGBM 一层一层遍历

public class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int value) {
        this.value = value;
    }
}

节点的结构如上

下面案例构造的树结构如下图

public class Demo1 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println("先序遍历顺序是：");
        recursivePreOrder(node1); //先序遍历
        System.out.println();
        System.out.println("中序遍历顺序是：");
        recursiveInOrder(node1);
        System.out.println();
        System.out.println("后序遍历顺序是：");
        recursivePostOrder(node1);

    }

    //先序遍历  根 左  右
    public static void recursivePreOrder(Node head){
        if(head == null){
            return;
        }
        System.out.print(head.value+" ");
        recursivePreOrder(head.left);
        recursivePreOrder(head.right);
    }

    //中序遍历
    public static void recursiveInOrder(Node head){
        if(head == null){
            return;
        }
        recursiveInOrder(head.left);
        System.out.print(head.value+" ");
        recursiveInOrder(head.right);
    }

    //后序遍历
    public static void recursivePostOrder(Node head){
        if(head == null){
            return;
        }
        recursivePostOrder(head.left);
        recursivePostOrder(head.right);
        System.out.print(head.value+" ");
    }
}

输出：
先序遍历顺序是：
1 2 4 5 3 6 7
中序遍历顺序是：
4 2 5 1 6 3 7
后序遍历顺序是：
4 5 2 6 7 3 1

函数体

 public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println("先序遍历顺序是：");
        recursivePreOrder(node1); //先序遍历
        System.out.println();
        System.out.println("中序遍历顺序是：");
        recursiveInOrder(node1);
        System.out.println();
        System.out.println("后序遍历顺序是：");
        recursivePostOrder(node1);
    }

    
    public static void recursivePreOrder(Node head){
        Stack stack = new Stack<>();
        stack.push(head);  //根节点入栈
        while (!stack.isEmpty()){
            Node cur = stack.pop(); //弹出一个节点
            System.out.print(cur.value+" ");  //打印弹出节点
            if(cur.right != null){  //弹出节点如果存在右节点,右节点入栈
                stack.push(cur.right);
            }
            if(cur.left != null){   //弹出节点如果存在左节点,左节点入栈
                stack.push(cur.left);
            }
        }
    }

 
    public static void recursiveInOrder(Node head){

        if(head != null){
            Stack stack = new Stack<>();
            while (!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    System.out.print(head.value+" ");
                    head = head.right;
                }
            }
        }

    }

 
    public static void recursivePostOrder(Node head){
        Stack stack = new Stack<>();
        Stack collectionStack = new Stack<>();   //收集栈
        stack.push(head);   //头节点入栈
        while (!stack.isEmpty()){
            Node cur = stack.pop(); //弹出一个节点
            collectionStack.push(cur);  //将弹出节点放入收集栈中
            if(cur.left != null){
                stack.push(cur.left);   //弹出节点如果存在左节点,左节点入栈
            }
            if(cur.right != null){
                stack.push(cur.right);  //弹出节点如果存在右节点,右节点入栈
            }
        }
        //在将收集栈中的所有数据弹出
        while (!collectionStack.isEmpty()){
            System.out.print(collectionStack.pop().value+" ");
        }

    }

    
    public static void widthOrder(Node head){
        if(head != null){
            linkedList linkedList = new linkedList<>();
            linkedList.add(head);   //头节点入队
            while (!linkedList.isEmpty()){
                Node cur = linkedList.poll();    //队头元素出队
                System.out.print(cur.value+" ");
                if(cur.left != null){   //假如出队元素有左节点  左节点进队
                    linkedList.add(cur.left);
                }
                if(cur.right != null){  //假如出队元素有右节点  右节点进队
                    linkedList.add(cur.right);
                }
            }
        }else{
            return;
        }
    }

输出：
先序遍历顺序是：
1 2 4 5 3 6 7
中序遍历顺序是：
4 2 5 1 6 3 7
后序遍历顺序是：
4 5 2 6 7 3 1
层次遍历顺序是:
1 2 3 4 5 6 7