本来就是基础知识，不能丢的太干净，今天竟然花了那么长的时间才写出来，记一下。
有如下的一颗完全二叉树：
先序遍历结果应该为：1 2 4 5 3 6 7
中序遍历结果应该为：4 2 5 1 6 3 7
后序遍历结果应该为：4 5 2 6 7 3 1
层序遍历结果应该为：1 2 3 4 5 6 7
二叉树的先序遍历、中序遍历、后序遍历其实都是一样的，都是执行递归操作。
我这记录一下层次遍历吧：层次遍历需要用到队列，先入队在出队，每次出队的元素检查是其是否有左右孩子，有则将其加入队列，由于利用队列的先进先出原理，进行层次遍历。
下面记录下完整代码（Java实现），包括几种遍历方法：
java" id="highlighter_865772">
|
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;/** * 定义二叉树节点元素 * @author bubble * */class Node { public Node leftchild; public Node rightchild; public int data; public Node(int data) { this.data = data; }}public class TestBinTree { /** * 将一个arry数组构建成一个完全二叉树 * @param arr 需要构建的数组 * @return 二叉树的根节点 */ public Node initBinTree(int[] arr) { if(arr.length == 1) { return new Node(arr[0]); } List<Node> nodeList = new ArrayList<>(); for(int i = 0; i < arr.length; i++) { nodeList.add(new Node(arr[i])); } int temp = 0; while(temp <= (arr.length - 2) / 2) { //注意这里，数组的下标是从零开始的 if(2 * temp + 1 < arr.length) { nodeList.get(temp).leftchild = nodeList.get(2 * temp + 1); } if(2 * temp + 2 < arr.length) { nodeList.get(temp).rightchild = nodeList.get(2 * temp + 2); } temp++; } return nodeList.get(0); } /** * 层序遍历二叉树，，并分层打印 * @param root 二叉树根节点 * */ public void trivalBinTree(Node root) { Queue<Node> nodeQueue = new ArrayDeque<>(); nodeQueue.add(root); Node temp = null; int currentLevel = 1; //记录当前层需要打印的节点的数量 int nextLevel = 0;//记录下一层需要打印的节点的数量 while ((temp = nodeQueue.poll()) != null) { if (temp.leftchild != null) { nodeQueue.add(temp.leftchild); nextLevel++; } if (temp.rightchild != null) { nodeQueue.add(temp.rightchild); nextLevel++; } System.out.print(temp.data + " "); currentLevel--; if(currentLevel == 0) { System.out.println(); currentLevel = nextLevel; nextLevel = 0; } } } /** * 先序遍历 * @param root 二叉树根节点 */ public void preTrival(Node root) { if(root == null) { return; } System.out.print(root.data + " "); preTrival(root.leftchild); preTrival(root.rightchild); } /** * 中序遍历 * @param root 二叉树根节点 */ public void midTrival(Node root) { if(root == null) { return; } midTrival(root.leftchild); System.out.print(root.data + " "); midTrival(root.rightchild); } /** * 后序遍历 * @param root 二叉树根节点 */ public void afterTrival(Node root) { if(root == null) { return; } afterTrival(root.leftchild); afterTrival(root.rightchild); System.out.print(root.data + " "); } public static void main(String[] args) { TestBinTree btree = new TestBinTree(); int[] arr = new int[] {1,2,3,4,5,6,7}; Node root = btree.initBinTree(arr); System.out.println("层序遍历(分层打印)："); btree.trivalBinTree(root); System.out.println("\n先序遍历："); btree.preTrival(root); System.out.println("\n中序遍历："); btree.midTrival(root); System.out.println("\n后序遍历："); btree.afterTrival(root); } } |
遍历结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://www.cnblogs.com/gonjan-blog/p/6504668.html
