数据结构与算法-二叉树前序、中序、后序、层序遍历

二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

序言

二叉树的遍历方式主要有：先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序指的是父节点被访问的次序。本篇文章将用java代码实现下图中的二叉树的遍历

数据结构二叉树

创建图中节点

public class TreeNode<T> {
    private T data;
    private TreeNode left;
    private TreeNode right;
}

TreeNode treeNodeA = new TreeNode("A");
TreeNode treeNodeB = new TreeNode("B");
TreeNode treeNodeC = new TreeNode("C");
TreeNode treeNodeD = new TreeNode("D");
TreeNode treeNodeE = new TreeNode("E");
TreeNode treeNodeF = new TreeNode("F");
        
treeNodeA.setLeft(treeNodeB);
treeNodeA.setRight(treeNodeC);

treeNodeB.setLeft(treeNodeD);
treeNodeB.setRight(treeNodeE);

treeNodeC.setLeft(treeNodeF);

前序遍历

遍历思路:在遍历过程中，父节点先于它的子节点被访问(父节点 -> 左子树 -> 右子树)

前序遍历代码

    private void preOrderTraverse(TreeNode treeNode, VisitListener visitListener) {
        if (treeNode == null) {
            return;
        }
        visitListener.visit(treeNode.getData());
        preOrderTraverse(treeNode.getLeft(), visitListener);
        preOrderTraverse(treeNode.getRight(), visitListener);
    }

测试代码

        preOrderTraverse(treeNodeA, new VisitListener<String>() {
            @Override
            public void visit(String treeNodeData) {
                Log.d("TAG", treeNodeData);
            }
        });

输出

2020-05-25 21:32:40.508 16157-16157/? D/TAG: A
2020-05-25 21:32:40.508 16157-16157/? D/TAG: B
2020-05-25 21:32:40.508 16157-16157/? D/TAG: D
2020-05-25 21:32:40.508 16157-16157/? D/TAG: E
2020-05-25 21:32:40.508 16157-16157/? D/TAG: C
2020-05-25 21:32:40.508 16157-16157/? D/TAG: F

中序遍历

遍历思路:在遍历过程中，父节点被访问的次序位于左右子节点之间( 左子树 -> 父节点 ->右子树)

中序遍历代码

    private void infixOrderTraverse(TreeNode treeNode, VisitListener visitListener) {
        if (treeNode == null) {
            return;
        }
        infixOrderTraverse(treeNode.getLeft(), visitListener);
        visitListener.visit(treeNode.getData());
        infixOrderTraverse(treeNode.getRight(), visitListener);
    }

测试代码

        infixOrderTraverse(treeNodeA, new VisitListener<String>() {
            @Override
            public void visit(String treeNodeData) {
                Log.d("TAG", treeNodeData);
            }
        });

输出

2020-05-25 21:32:40.508 16157-16157/? D/TAG: D
2020-05-25 21:32:40.508 16157-16157/? D/TAG: B
2020-05-25 21:32:40.508 16157-16157/? D/TAG: E
2020-05-25 21:32:40.508 16157-16157/? D/TAG: A
2020-05-25 21:32:40.508 16157-16157/? D/TAG: F
2020-05-25 21:32:40.508 16157-16157/? D/TAG: C

后序遍历

遍历思路:在遍历过程中，访问完左右子节点之后再访问父节点( 左子树 ->右子树 -> 父节点)

后序遍历代码

    private void epilogueOrderTraverse(TreeNode treeNode, VisitListener visitListener) {
        if (treeNode == null) {
            return;
        }
        epilogueOrderTraverse(treeNode.getLeft(), visitListener);
        epilogueOrderTraverse(treeNode.getRight(), visitListener);
        visitListener.visit(treeNode.getData());
    }

测试代码

        epilogueOrderTraverse(treeNodeA, new VisitListener<String>() {
            @Override
            public void visit(String treeNodeData) {
                Log.d("TAG", treeNodeData);
            }
        });

输出

2020-05-25 21:32:40.508 16157-16157/? D/TAG: D
2020-05-25 21:32:40.508 16157-16157/? D/TAG: E
2020-05-25 21:32:40.508 16157-16157/? D/TAG: B
2020-05-25 21:32:40.508 16157-16157/? D/TAG: F
2020-05-25 21:32:40.508 16157-16157/? D/TAG: C
2020-05-25 21:32:40.508 16157-16157/? D/TAG: A

层序遍历

遍历思路:在遍历过程中，按照从上到下、从左向右的顺序访问二叉树的每个节点

层序遍历代码

    private void levelOrderTraverse(TreeNode treeNode, VisitListener visitListener) {
        if (treeNode == null) {
            return;
        }
        Queue<TreeNode> treeNodeQueue = new ArrayDeque<>();
        treeNodeQueue.add(treeNode);
        TreeNode currentNode;
        while (!treeNodeQueue.isEmpty()) {
            currentNode = treeNodeQueue.peek();
            visitListener.visit(currentNode.getData());
            if (currentNode.getLeft() != null) {
                treeNodeQueue.add(currentNode.getLeft());
            }
            if (currentNode.getRight() != null) {
                treeNodeQueue.add(currentNode.getRight());
            }
            treeNodeQueue.poll();
        }
    }

测试代码

        levelOrderTraverse(treeNodeA, new VisitListener<String>() {
            @Override
            public void visit(String treeNodeData) {
                Log.d("TAG", treeNodeData);
            }
        });

输出

2020-05-25 21:32:40.508 16157-16157/? D/TAG: A
2020-05-25 21:32:40.508 16157-16157/? D/TAG: B
2020-05-25 21:32:40.508 16157-16157/? D/TAG: C
2020-05-25 21:32:40.508 16157-16157/? D/TAG: D
2020-05-25 21:32:40.508 16157-16157/? D/TAG: E
2020-05-25 21:32:40.508 16157-16157/? D/TAG: F