二叉树的遍历-先序遍历、中序遍历、后序遍历_二叉树遍历前序中序后序

树的遍历-先序遍历、中序遍历、后序遍历

二叉树遍历方式

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

常见的四种遍历方式分别为：先序遍历、中序遍历、后序遍历、层序遍历。

• 先序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。
• 中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。
• 后序遍历：先遍历左子树，然后遍历右子树，最后遍历根结点。
• 层序遍历：按层次顺序访问二叉树的每一个节点。

先序遍历

二叉树的先序遍历，就是先输出根结点，再遍历左子树，最后遍历右子树，遍历左子树和右子树的时候，同样遵循先序遍历的规则。

/**
     * 先序遍历
     * @param treeNode
     */
    public void preOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        System.out.print(" " + treeNode.value);
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12

中序遍历

二叉树的中序遍历，就是先递归中序遍历左子树，再输出根结点的值，再递归中序遍历右子树。

    /**
     * 中序遍历
     * @param treeNode
     */
    public void inOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        inOrder(treeNode.left);
        System.out.print(" " + treeNode.value);
        inOrder(treeNode.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12

后序遍历

二叉树的后序遍历，就是先递归后序遍历左子树，再递归后序遍历右子树，最后输出根结点的值。

 /**
     * 后序遍历
     * @param treeNode
     */
    public void postOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        postOrder(treeNode.left);
        postOrder(treeNode.right);
        System.out.print(" " + treeNode.value);
    }
1
2
3
4
5
6
7
8
9
10
11
12

案例：

public class TreeDemo {

    public class TreeNode{
        private Integer value;
        private TreeNode right;
        private TreeNode left;

        public TreeNode() {
        }

        public TreeNode(Integer value, TreeNode left, TreeNode right) {
            this.value = value;
            this.right = right;
            this.left = left;
        }

        public Integer getvalue() {
            return value;
        }

        public void setvalue(Integer value) {
            this.value = value;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }
    }

    public static void main(String[] args) {
        TreeDemo treeDemo = new TreeDemo();
        TreeNode tree = treeDemo.getTree();
        System.out.println("先序遍历:");
        treeDemo.preOrder(tree);
        System.out.println();
        System.out.println("中序遍历:");
        treeDemo.inOrder(tree);
        System.out.println();
        System.out.println("后序遍历:");
        treeDemo.postOrder(tree);
    }

    public TreeNode getTree(){
        TreeNode treeNode = new TreeNode();
        treeNode.setvalue(13);
        treeNode.setLeft(new TreeNode(10,
                new TreeNode(7,
                new TreeNode(3,null,null),new TreeNode(4,null,null)),
                new TreeNode(12,new TreeNode(11,null,null),null)));


        treeNode.setRight(new TreeNode(15,
                new TreeNode(14,null,null),
                new TreeNode(17,null,null)));
        return treeNode;
    }

    /**
     * 先序遍历
     * @param treeNode
     */
    public void preOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        System.out.print(" " + treeNode.value);
        preOrder(treeNode.left);
        preOrder(treeNode.right);
    }

    /**
     * 中序遍历
     * @param treeNode
     */
    public void inOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        inOrder(treeNode.left);
        System.out.print(" " + treeNode.value);
        inOrder(treeNode.right);
    }

    /**
     * 后序遍历
     * @param treeNode
     */
    public void postOrder(TreeNode treeNode){
        if(treeNode == null){
            return;
        }
        postOrder(treeNode.left);
        postOrder(treeNode.right);
        System.out.print(" " + treeNode.value);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

结果如下：