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