二叉树的遍历递归和非递归

二叉树的遍历是解决树类问题的关键，二叉树的遍历分为递归和非递归。一般来说，递归的非递归的简单许多，但是一般要求能够写出非递归的代码，并且讲清楚非递归的算法思想。

1.二叉树的数据结构

image.png

package com.zhoujian.solutions.dataStructure.tree;
/**
 * @author zhoujian 2018/8/18
 */
public class Node {
    public int value;
    public Node left;
    public Node right;
    //构造器
    public Node(int value) {
        this.value = value;
    }
}

这是二叉树的节点的数据类型结构。

2.二叉树的遍历（递归）

package com.zhoujian.solutions.dataStructure.tree;

/**
 * @author zhoujian123@hotmail.com 2018/4/30 21:27
 *
 * 二叉树的遍历递归和非递归方式
 */
public class BinaryTree {
    public static void preOrder(Node head){
        if (head == null) {
            return;
        }
        System.out.print(head.value);
        preOrder(head.left);
        preOrder(head.right);
    }
    public static void inOrder(Node head){
        if (head == null) {
            return;
        }
        preOrder(head.left);
        System.out.print(head.value);
        preOrder(head.right);
    }
    public static void postOrder(Node head){
        if (head == null) {
            return;
        }
        preOrder(head.left);
        preOrder(head.right);
        System.out.print(head.value);
    }
    public static void main(String[] args) {
        //根节点是5
        Node node =new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.left = new Node(6);
        node.right.right = new Node(7);
        System.out.println("先序遍历");
        preOrder(node);
        System.out.println();
        System.out.println("中序遍历");
        inOrder(node);
        System.out.println();
        System.out.println("后序遍历");
        postOrder(node);

    }
}

3.二叉树的遍历（非递归）

package com.zhoujian.solutions.dataStructure.tree;

import java.util.Stack;

/**
 * @author zhoujian 2018/8/18
 */
public class BinaryTreeTest {
    //前序遍历的思想：借助一个栈，先放入右孩子，在放做孩子。在从栈顶弹出栈顶元素，查看当前元素有没有左右孩 //子。
    public static void proOrderunRecur(Node head){
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);
            while (!stack.isEmpty()){
                //不为空先弹出栈顶元素
                head = stack.pop();
                System.out.print(head.value);
                //先看有没有右孩子
                if(head.right !=null){
                    stack.push(head.right);
                }
                //在看有没有左孩子
                if(head.left != null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    //中序遍历：借助一个栈，若该节点不是叶子节点，就一直循环线找到最左的孩子，直到叶子节点，然后弹出栈顶元   //素，查看该节点有没有右孩子。若有，则将右孩子压入栈中。若没有，则继续弹出栈顶元素。
    public static void inOrderunRecur(Node head){
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            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 posOrderunRecur(Node head){
        if (head != null) {
            Stack<Node> stack1 = new Stack<Node>();
            Stack<Node> stack2 = new Stack<Node>();
            //先将栈顶元素压入栈中
            stack1.push(head);
            while (!stack1.isEmpty()){
                //从stack1中弹出栈顶元素，放入到stack2中
                head = stack1.pop();
                stack2.push(head);
                if (head.left != null) {
                    stack1.push(head.left);
                }
                if (head.right != null) {
                    stack1.push(head.right);
                }
            }
            //从栈中依次打印出来，打印出来的顺序就是后序遍历
            while (!stack2.isEmpty()){
                System.out.print(stack2.pop().value);
            }
        }

    }

    public static void main(String[] args) {
        //根节点是5
        Node node =new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.left = new Node(6);
        node.right.right = new Node(7);
        System.out.println("前序遍历");
        proOrderunRecur(node);
        System.out.println("中序遍历");
        inOrderunRecur(node);
        System.out.println();
        System.out.println("后序遍历");
        posOrderunRecur(node);
    }
}

后序遍历有点复杂：

image.png
image.png image.png