二元樹的前序、中序、後序遍歷（遞迴版）

二元樹是一種非常重要的資料結構，很多其它資料結構都是基於二元樹的基礎演變而來的。

1、二元樹的遍歷方法

對於二元樹，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及後序三種遍歷方法，廣度遍歷即我們平常所說的層次遍歷。

因為樹的定義本身就是遞迴定義，因此採用遞迴的方法去實現樹的三種遍歷不僅容易理解而且程式碼很簡潔，而對於廣度遍歷來說，需要其他資料結構的支撐，比如堆。所以，對於一段程式碼來說，可讀性有時候要比程式碼本身的效率要重要的多。

所謂前序，中序，後續遍歷命名的由來是我們存取二元樹，根節點的順序。前序遍歷就是優先存取根節點，中序遍歷是第二個存取根節點，後續遍歷就是存取完左右節點之後，最後存取根節點。

注意存取二字。存取和獲取是兩個不同的概念，我們可以獲取一個節點，但是不存取他。對應在計算機裡的概念是，獲取一個節點表示將他入棧，存取一個節點是他處於棧頂，我們即將讓他出棧。

2、前序遍歷（先序遍歷）

前序遍歷，就是優先存取根節點，然後存取左子節點，最後存取右子節點。說簡單點就是：根左右。

直接上程式碼：

 1 public class TreeNode<N> implements Serializable {
 2 
 3     private N val;
 4 
 5     private TreeNode<N> left;
 6 
 7     private TreeNode<N> right;
 8 
 9     public TreeNode() {
10     }
11 
12     public TreeNode(N val) {
13         this.val = val;
14     }
15 
16     public TreeNode(N val, N leftVal, N rightVal) {
17         this.val = val;
18         this.left = new TreeNode<>(leftVal);
19         this.right = new TreeNode<>(rightVal);
20     }
21 
22     public N getVal() {
23         return val;
24     }
25 
26     public void setVal(N val) {
27         this.val = val;
28     }
29 
30     public TreeNode<N> getLeft() {
31         return left;
32     }
33 
34     public void setLeft(N left) {
35         this.left = new TreeNode<>(left);
36     }
37 
38     public TreeNode<N> getRight() {
39         return right;
40     }
41 
42     public void setRight(N right) {
43         this.right = new TreeNode<>(right);
44     }
45 }
46 
47 
48 public class treeTest {
49 
50     public static void main(String[] args) {
51         Queue<TreeNode<Integer>> queue = new LinkedList<>();
52         TreeNode<Integer> root = new TreeNode<>(0);
53         root.setLeft(1);
54         root.setRight(2);
55         root.getLeft().setLeft(3);
56         root.getLeft().setRight(4);
57         root.getRight().setLeft(5);
58         root.getRight().setRight(6);
59         System.out.println("   " + root.getVal());
60         System.out.println("  /  \\");
61         System.out.println(" " + root.getLeft().getVal() + "    " + root.getRight().getVal());
62         System.out.println("/ \\  / \\");
63         System.out.println(root.getLeft().getLeft().getVal() + " " +  root.getLeft().getRight().getVal() + "  "
64                 + root.getRight().getLeft().getVal() + "  " + root.getRight().getRight().getVal());
65 
66 
67 
68         List<Integer> qianXu = qian(root);
69         System.out.println(qianXu);
70     }
71 
72     private static List<Integer> qian(TreeNode<Integer> root) {
73         List<Integer> resut = new ArrayList<>();
74 
75         if(null == root) return resut;
76 
77         resut.add(root.getVal());
78         resut.addAll(qian(root.getLeft()));
79         resut.addAll(qian(root.getRight()));
80 
81         return resut;
82     }
83 }

前序遍歷

輸出結果：

3、中序遍歷

中序遍歷，就是優先存取左子節點，然後存取根節點，最後存取右子節點。說簡單點就是：左根右。

範例程式碼：

 1 public class TreeNode<N> implements Serializable {
 2 
 3     private N val;
 4 
 5     private TreeNode<N> left;
 6 
 7     private TreeNode<N> right;
 8 
 9     public TreeNode() {
10     }
11 
12     public TreeNode(N val) {
13         this.val = val;
14     }
15 
16     public TreeNode(N val, N leftVal, N rightVal) {
17         this.val = val;
18         this.left = new TreeNode<>(leftVal);
19         this.right = new TreeNode<>(rightVal);
20     }
21 
22     public N getVal() {
23         return val;
24     }
25 
26     public void setVal(N val) {
27         this.val = val;
28     }
29 
30     public TreeNode<N> getLeft() {
31         return left;
32     }
33 
34     public void setLeft(N left) {
35         this.left = new TreeNode<>(left);
36     }
37 
38     public TreeNode<N> getRight() {
39         return right;
40     }
41 
42     public void setRight(N right) {
43         this.right = new TreeNode<>(right);
44     }
45 }
46 
47 
48 
49 public class treeTest {
50 
51     public static void main(String[] args) {
52         Queue<TreeNode<Integer>> queue = new LinkedList<>();
53         TreeNode<Integer> root = new TreeNode<>(0);
54         root.setLeft(1);
55         root.setRight(2);
56         root.getLeft().setLeft(3);
57         root.getLeft().setRight(4);
58         root.getRight().setLeft(5);
59         root.getRight().setRight(6);
60         System.out.println("   " + root.getVal());
61         System.out.println("  /  \\");
62         System.out.println(" " + root.getLeft().getVal() + "    " + root.getRight().getVal());
63         System.out.println("/ \\  / \\");
64         System.out.println(root.getLeft().getLeft().getVal() + " " +  root.getLeft().getRight().getVal() + "  "
65                 + root.getRight().getLeft().getVal() + "  " + root.getRight().getRight().getVal());
66 
67         List<Integer> zhongXu = zhong(root);
68         System.out.println(zhongXu);
69     }
70 
71     private static List<Integer> zhong(TreeNode<Integer> root) {
72         List<Integer> resut = new ArrayList<>();
73 
74         if(null == root) return resut;
75 
76         resut.addAll(zhong(root.getLeft()));
77         resut.add(root.getVal());
78         resut.addAll(zhong(root.getRight()));
79 
80         return resut;
81     }
82 }

中序遍歷

輸出結果：

4、後序遍歷

後序遍歷，就是優先存取左子節點，然後存取右子節點，最後存取根節點。說簡單點就是：左右根。

範例程式碼：

 1 public class TreeNode<N> implements Serializable {
 2 
 3     private N val;
 4 
 5     private TreeNode<N> left;
 6 
 7     private TreeNode<N> right;
 8 
 9     public TreeNode() {
10     }
11 
12     public TreeNode(N val) {
13         this.val = val;
14     }
15 
16     public TreeNode(N val, N leftVal, N rightVal) {
17         this.val = val;
18         this.left = new TreeNode<>(leftVal);
19         this.right = new TreeNode<>(rightVal);
20     }
21 
22     public N getVal() {
23         return val;
24     }
25 
26     public void setVal(N val) {
27         this.val = val;
28     }
29 
30     public TreeNode<N> getLeft() {
31         return left;
32     }
33 
34     public void setLeft(N left) {
35         this.left = new TreeNode<>(left);
36     }
37 
38     public TreeNode<N> getRight() {
39         return right;
40     }
41 
42     public void setRight(N right) {
43         this.right = new TreeNode<>(right);
44     }
45 }
46 
47 
48 public class treeTest {
49 
50     public static void main(String[] args) {
51         Queue<TreeNode<Integer>> queue = new LinkedList<>();
52         TreeNode<Integer> root = new TreeNode<>(0);
53         root.setLeft(1);
54         root.setRight(2);
55         root.getLeft().setLeft(3);
56         root.getLeft().setRight(4);
57         root.getRight().setLeft(5);
58         root.getRight().setRight(6);
59         System.out.println("   " + root.getVal());
60         System.out.println("  /  \\");
61         System.out.println(" " + root.getLeft().getVal() + "    " + root.getRight().getVal());
62         System.out.println("/ \\  / \\");
63         System.out.println(root.getLeft().getLeft().getVal() + " " +  root.getLeft().getRight().getVal() + "  "
64                 + root.getRight().getLeft().getVal() + "  " + root.getRight().getRight().getVal());
65 
66         List<Integer> houXu = hou(root);
67         System.out.println(houXu);
68     }
69 
70     private static List<Integer> hou(TreeNode<Integer> root) {
71         List<Integer> resut = new ArrayList<>();
72 
73         if(null == root) return resut;
74 
75         resut.addAll(hou(root.getLeft()));
76         resut.addAll(hou(root.getRight()));
77         resut.add(root.getVal());
78 
79         return resut;
80     }
81 }

後序遍歷

輸出結果：