1.左邊<中間<右邊
2.前序遍歷 左中右
3.中序遍歷 中左右
4.后序遍歷 左右中
|
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
|
public class BinaryTree { // 二叉樹的根節點 public TreeNode rootNode ; // 記錄搜索深度 public int count; /** * 利用傳入一個數組來建立二叉樹 */ public BinaryTree(int[] data) { for (int i = 0; i < data. length; i++) { addNodeToTree(data[i]); } } /** * 將指定的值加入到二叉樹中適當的節點 */ private void addNodeToTree(int value) { TreeNode currentNode = rootNode; // 建立樹根 if (rootNode == null) { rootNode = new TreeNode(value); return; } // 建立二叉樹 while (true) { // 新增的value比節點的value小，則在左子樹 if (value < currentNode.value ) { if (currentNode.leftNode == null) { currentNode.leftNode = new TreeNode(value); return; } else { currentNode = currentNode.leftNode; } } else { // 新增的value比節點的value大，在右子樹 if (currentNode.rightNode == null) { currentNode. rightNode = new TreeNode(value); return; } else { currentNode = currentNode. rightNode; } } } } /** * 中序遍歷(左子樹 -樹根- 右子樹) */ public void inOrder(TreeNode node) { if (node != null) { inOrder(node. leftNode); System. out.print("[" + node.value + "]"); inOrder(node. rightNode); } } /** * 前序遍歷(樹根 -左子樹- 右子樹) */ public void preOrder(TreeNode node) { if (node != null) { System. out.print("[" + node.value + "]"); preOrder(node. leftNode); preOrder(node. rightNode); } } /** * 后序遍歷(左子樹 -右子樹- 樹根) */ public void postOrder(TreeNode node) { if (node != null) { postOrder(node. leftNode); postOrder(node. rightNode); System. out.print("[" + node.value + "]"); } } /** * 從二叉樹中查找指定value */ public boolean findTree(TreeNode node, int value) { if (node == null) { System. out.println("共搜索" + count + "次"); return false; } else if (node.value == value) { System. out.println("共搜索" + count + "次"); return true; } else if (value < node.value) { count++; return findTree(node.leftNode , value); } else { count++; return findTree(node.rightNode , value); } } /** * 利用中序遍歷進行排序 */ public void sort() { this.inOrder(rootNode ); } class TreeNode { int value ; TreeNode leftNode; TreeNode rightNode; public TreeNode(int value) { this.value = value; this.leftNode = null; this.rightNode = null; } } public static void main(String[] args) { int[] content = { 50, 35, 27, 45, 40, 48, 78, 56, 90 }; BinaryTree tree = new BinaryTree(content); System. out.println("前序遍歷:" ); tree.preOrder(tree. rootNode); System. out.println("\n中序遍歷:" ); tree.inOrder(tree. rootNode); System. out.println("\n后序遍歷:" ); tree.postOrder(tree. rootNode); System. out.println("\n\n開始搜索:" ); boolean isFind = tree.findTree(tree.rootNode, 48); System. out.println("是否搜索到" + 48 + ":" + isFind); System. out.println("\n進行排序:" ); tree.sort(); }} |
前序遍歷:
|
1
|
[50][35][27][45][40][48][78][56][90] |
中序遍歷:
|
1
|
[27][35][40][45][48][50][56][78][90] |
后序遍歷:
|
1
|
[27][40][48][45][35][56][90][78][50] |
開始搜索:
共搜索3次
是否搜索到48:true
進行排序:
|
1
|
[27][35][40][45][48][50][56][78][90] |
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：https://my.oschina.net/u/1037605/blog/775018
