Java 二叉树的遍历

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。

前序遍历（根 左 右）

先访问根结点，然后前序遍历左子树，再前序遍历右子树

中序遍历（左 根 右）

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

后序遍历（左 右 根）

从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点

层级遍历（从上到下 从左到右）

从根结点从上往下从左往右依次遍历

思路

非递归：

前序遍历：从根节点开始，首先将根节点压入栈中，栈不为空进行出栈并打印结点的value数值，然后将该结点的不为空的右结点和左结点依次进行入栈操作重复直到栈为空。

后序遍历：从根节点开始，首先将根节点压入栈中，栈不为空进行出栈并入栈到另一个栈中，然后将该结点的不为空的左结点和右结点依次进行入栈操作重复直到栈为空。然后遍历另一个栈进行出栈并打印结点的值。

中序遍历：从根节点开始将该结点以及它的左边界依次进行入栈，当该结点为null时，然后进行出栈操作，打印出栈结点的value数值，并入栈弹出结点的右结点，然后重复上述步骤，继续入栈该结点的左边界直到为空。。。。

层次遍历：从根节点放入队列，队列不为空的时候进行出队列并打印该结点的value数值，然后依次将该结点的左结点和右结点进行放入队列，一直重复直到队列为空。

代码

Node结点

public class Node<V> {
    V value;

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

    public Node left;
    public Node right;
}

遍历代码

public class Tree {
    //递归先序遍历
    public static void preOrder1(Node head){
        if(head!=null){
            System.out.print(head.value+" ");
            preOrder1(head.left);
            preOrder1(head.right);
        }
    }

    //先序遍历
    public static void preOrder(Node head){
        if(head!=null){
            Stack<Node> stack=new Stack<>();
            stack.add(head);//压到栈尾
            while (!stack.empty()){
                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 postOrder(Node head){
        if(head!=null){
            Stack<Node> stack1=new Stack<>();
            Stack<Node> stack2=new Stack<>();
            stack1.push(head);
            while (!stack1.empty()){
                head = stack1.pop();
                stack2.push(head);
                if(head.left!=null)
                    stack1.push(head.left);
                if(head.right!=null)
                stack1.push(head.right);

            }
            while (!stack2.empty()){
                Node pop = stack2.pop();
                System.out.print(pop.value+" ");
            }
            System.out.println();
        }
    }
    //中序遍历
    public static void inOrder(Node head){
            Stack<Node> stack=new Stack<>();
            while (!stack.empty()||head!=null){
                if(head!=null){
                    stack.push(head);
                    head=head.left;
                }
                else {
                    head=stack.pop();
                    System.out.print(head.value+" ");
                    head=head.right;
                }
            }
        System.out.println();
    }

    //层次遍历
    public static void widthOrder(Node head){
        if(head!=null){
            Queue<Node> queue=new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()){
                Node poll = queue.poll();
                System.out.print(poll.value+" ");
                if(poll.left!=null)
                    queue.add(poll.left);
                if(poll.right!=null){
                    queue.add(poll.right);
                }
            }
        }
        System.out.println();
    }


}

求二叉树的高度（引用）

方法一：递归遍历

比较左右子树的高度，谁的高度高，则树的高度则为：1+子数高度较高的；

public int height(){
        return height(root);
    }
    public int height(Node<E> node){
        if (node == null) return 0;
       return 1 + Math.max(height(node.left),height(node.right));
    }

方法二:非递归

采用层次遍历

 public int getTreeHeight(){
        if (root == null ) return 0;
        Queue<Node<E>> queue = new LinkedList();
        queue.offer(root);
        int levelNum = 1;   //存取层的节点树
        int height = 0;
        while(!queue.isEmpty()){
            Node<E> node =  queue.poll();//出队
            levelNum--;//有多少个节点就遍历多少次
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
            //levelNum默认为1（只要根节点不为空，高度自然从1开始）
            //每回遍历完一层，queue的大小为下一层节点的数目
            if (levelNum == 0){
                levelNum = queue.size();
                height++;
            }
        }
        return height;
    }