[数据结构与算法]算法_二叉树遍历篇

Java二叉树遍历篇

通过二叉树的前序、中序、后序遍历以及层序遍历等方式，理解二叉树的结构思想。

二叉树定义

public class TreeNode {
    /** 根节点*/
    int val;
    /** 左节点*/
    TreeNode left;
    /** 右节点*/
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

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

在下述前中后序开始前，有一个操作类

public class BinaryTreeOP {
/** 二叉树的开始都是从根节点开始 */
    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }
}

一、前序遍历

前序的规则就是根结点 —> 左子树 —> 右子树.我们在调用递归前进行节点操作。对于前序，就是先访问(输出)该节点。而递归左，递归右侧，会优先递归左侧。直到没有左节点。

//    前序遍历 TreeNode.java
    public void Pre_orderTraversal() {
//        先输出父节点
        System.out.println(this);
        if (this.left!=null){
            this.left.Pre_orderTraversal();
        }
        if (this.right!=null){
            this.right.Pre_orderTraversal();
        }
    }

//    前序遍历 BinaryTreeOP.java
    public void preOrder(){
        if (this.root!=null){
            this.root.Pre_orderTraversal();
        }else {
            System.out.println("二叉树为空！");
        }
    }

二、中序遍历

中序遍历的规则是：左子树—> 根结点 —> 右子树

//    中序遍历 TreeNode.java
    public void In_orderTraversal(){
        if (this.left!=null){
            this.left.In_orderTraversal();
        }
//        输出父节点
        System.out.println(this);
        if (this.right!=null){
            this.right.In_orderTraversal();
        }
    }

 //    中序遍历  BinaryTreeOP.java
    public void inOrder(){
        if (this.root!=null){
            this.root.In_orderTraversal();
        }else {
            System.out.println("二叉树为空！");
        }
    }

三、后序遍历

后序遍历的规则是：左子树 —> 右子树 —> 根结点

//    后序遍历 TreeNode.java
    public void Post_orderTraversal(){
        if (this.left!=null){
            this.left.Post_orderTraversal();
        }
        if (this.right!=null){
            this.right.Post_orderTraversal();
        }
        System.out.println(this);
    }

//    后序遍历  BinaryTreeOP.java
    public void postOrder(){
        if (this.root!=null){
            this.root.Post_orderTraversal();
        }else {
            System.out.println("二叉树为空！");
        }
    }

四、层序遍历

层序遍历在树图理解上很好理解，就是一层一层遍历输出节点。但是在转化为算法实现时需要想一下。
事实上，通过BFS的思想也许能够有些帮助。广度优先遍历是按层层推进的方式，遍历每一层的节点。
具体实现时可以使用队列进行辅助。

/*
 * 广度层序遍历
 *   1
    / \
   2  3
    /  \
    4   5
 * */
    public List<List<Integer>> levelOrderBFS(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
//        队列存放根节点
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode currentNode = null;
        queue.offer(root);
        while (!queue.isEmpty()) {
            int cur = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
//            出队队头元素并访问
            for (int i = 0; i < cur; i++) {
                currentNode = queue.poll();
                tmp.add(currentNode.val);
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }