binary tree traversal

BinaryTreeTraversal.java

package al;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeTraversal {

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int v) {
            val = v;
        }
    }

    //获取二叉树的总节点数
    public static int size (TreeNode node) {
        if (node==null) {
            return 0;
        }
        return 1 + size(node.left) + size(node.right);
    }

    //前序遍历 递归实现
    public static void preOrderTraversalByRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(" " + node.val);

        preOrderTraversalByRecursion(node.left);
        preOrderTraversalByRecursion(node.right);
    }

    //中序遍历 递归实现
    public static void inOrderTraversalByRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraversalByRecursion(node.left);
        System.out.print(" " + node.val);
        inOrderTraversalByRecursion(node.right);
    }

    //后序遍历 递归实现
    public static void postOrderTraversalByRecursion(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrderTraversalByRecursion(node.left);
        postOrderTraversalByRecursion(node.right);
        System.out.print(" " + node.val);
    }

    //前序遍历 非递归 实现1
    public static void preOrderTraversal1(TreeNode root) {
        if (root==null) {
            return;
        }

        System.out.println();
        //初始化一个栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //首先将根节点压入栈中
        stack.push(root);

        while(stack.isEmpty()==false) {
            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);
            }
        }
        System.out.println();
    }

    //前序遍历 非递归 实现2
    public static void preOrderTraversal2(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.println();
        //初始化一个栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //建立一个临时节点
        TreeNode node = root;

        while (node != null || stack.isEmpty() == false) {

            while (node != null) {
                //输出节点
                System.out.print(" " +node.val);
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            node = node.right;
        }
        System.out.println();
    }

    //中序遍历 非递归
    public static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.println();
        //初始化一个栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //建立一个临时节点
        TreeNode node = root;

        while (node != null || stack.isEmpty() == false) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            //输出节点
            System.out.print(" " +node.val);

            node = node.right;
        }

        System.out.println();
    }

    //后序遍历 非递归
    public static void postOrderTraversal(TreeNode root){
        if (root == null) {
            return;
        }

        int size = size(root);

        System.out.println();
        //初始化一个栈
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //建立一个临时节点
        TreeNode node = root;
        //初始化一个数组 用于标示对应节点的右节点是否已经处理
        int[] flag = new int[size+1];

        while(node !=null) {
            stack.push(node);
            node = node.left;

            //初始化为0
            flag[stack.size()] = 0;
        }

        while(stack.isEmpty() ==false ) {
            node = stack.peek();
            while(node.right != null && flag[stack.size()] == 0) {
                //该节点的右节点有值 并且还没被处理过
                node = node.right;
                flag[stack.size()] = 1;

                while(node != null) {
                    stack.push(node);
                    node = node.left;
                    flag[stack.size()] = 0;
                }

                node = stack.peek();
            }

            node = stack.pop();
            //输出节点
            System.out.print(" " +node.val);
        }

        System.out.println();
    }

    //广度优先遍历
    public static void BFS(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.println();
        //初始化一个队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //将root根节点入队
        queue.offer(root);

        while(queue.isEmpty() == false) {
            //出队
            TreeNode node = queue.poll();
            System.out.print(" "+node.val);

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        System.out.println();
    }

    //按照前序遍历 中序遍历的顺序重建二叉树
    public static TreeNode RebuildBinaryTree(int[] preOrder, int[] inOrder,
                                                  int preStart, int preEnd,
                                                  int inStart, int inEnd) {

        if (preOrder == null || inOrder == null) {
            return null;
        }

        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }

        //前序遍历的第一个值 肯定是某个子树的根节点
        int v = preOrder[preStart];

        //在中序遍历中找到上面的值
        int idx=-1;
        for (int i=inStart; i <= inEnd; i++) {
            if (inOrder[i] == v) {
                idx = i;
                break;
            }
        }

        //如果没找到 说明不匹配
        if (idx < 0) {
            return null;
        }

        int step = idx - inStart;

        //这里的索引赋值比较关键
        TreeNode left = RebuildBinaryTree(preOrder, inOrder,
                preStart+1, preStart+step,
                inStart, idx-1);
        TreeNode right = RebuildBinaryTree(preOrder, inOrder,
                preStart+step+1, preEnd,
                idx+1, inEnd);

        TreeNode node = new TreeNode(v);
        node.left = left;
        node.right = right;

        return node;
    }

    public static void main(String... args) {
        //初始化
        int[] preOrder = {
                1,2,4,7,3,5,6,8
        };
        int[] inOrder = {
                4,7,2,1,5,3,8,6
        };
        TreeNode tree = RebuildBinaryTree(preOrder, inOrder,
                0, preOrder.length-1,
                0, inOrder.length-1);

        System.out.printf("\n前序 递归\n");
        preOrderTraversalByRecursion(tree);
        System.out.printf("\n前序 非递归1\n");
        preOrderTraversal1(tree);
        System.out.printf("\n前序 非递归2\n");
        preOrderTraversal2(tree);
        System.out.printf("\n中序 递归\n");
        inOrderTraversalByRecursion(tree);
        System.out.printf("\n中序 非递归\n");
        inOrderTraversal(tree);
        System.out.printf("\n后序 递归\n");
        postOrderTraversalByRecursion(tree);
        System.out.printf("\n后序 非递归\n");
        postOrderTraversal(tree);
        System.out.printf("\n广度遍历\n");
        BFS(tree);

    }
}