本文實例講述了java實現二叉樹的建立、計算高度與遞歸輸出操作。分享給大家供大家參考，具體如下：
1. 建立 遞歸輸出 計算高度 前中后三種非遞歸輸出
|
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
public class tree_link { private int save = 0; private int now = 0; scanner sc = new scanner(system.in); /* * 構造函數 */ tree_link(){ } /* * 鏈表建立 */ public tree link_build(tree head){// tree head = new tree();//頭節點 system.out.println("繼續code：1"); int flag = sc.nextint(); if(flag != 1){ return head; }else{ system.out.println("\n\n\n輸入 節點信息："); head.setcode(sc.nextint()); system.out.println("\n建立 左 子樹code：1 否則：0"); flag = sc.nextint(); if(flag == 1){ now++; tree ltree = new tree(); head.setltree(ltree); ltree.setfronttree(head);//設置父母節點 link_build( head.getltree() ); } system.out.println("\n當前位置：" + head.getcode()); system.out.println("\n建立 右 子樹code：1 否則：0"); flag = sc.nextint(); if(flag == 1){ now++; tree rtree = new tree(); head.setrtree(rtree); rtree.setfronttree(head);//設置父母節點 link_build( head.getrtree() ); } if( now > save ){ save = now; } now--; } return head; } /* * 輸出樹 */ public tree output(tree head){ int flag; if(head.getcode() == -1){ return head; }else{ system.out.println("\n當前位置：" + head.getcode()); system.out.println(head.getltree() != null); if(head.getltree() != null){ system.out.println("\n訪問 左子樹:"); output( head.getltree() ); } if(head.getrtree() != null){ system.out.println("\n訪問 右子樹:"); output( head.getrtree() ); } } return head; } /* * 獲得高度 */ public int getsave(){ return this.save; } /* * 非遞歸 前序遍歷 */ public void front_traverse(tree head){ tree star = head;//退出標記 int choose = 1; //左 int flag = 1; //右 system.out.println( "<---前序遍歷--->" + head.getcode() );//先訪問根 while(true){ if( head.getltree() != null && choose != 0 ){ head = head.getltree(); system.out.println( "<---前序遍歷--->" + head.getcode() );//獲得信息 flag = 1; }else if( head.getrtree() != null && flag != 0 ){ head = head.getrtree(); system.out.println( "<---前序遍歷--->" + head.getcode() ); choose = 1; }else if( flag == 0 && choose == 0 && head == star){ break; }else{ if(head == head.getfronttree().getrtree()){ flag = 0; choose = 0; } if(head == head.getfronttree().getltree()){ choose = 0; flag = 1; } head = head.getfronttree(); system.out.println("獲得 父母" + head.getcode()); system.out.println( "\n\n\n" ); } } } /* * 非遞歸 中序遍歷 */ public void center_traverse(tree head){ tree star = head;//退出標記 int choose = 1; //左 int flag = 1; //右 while(true){ if( head.getltree() != null && choose != 0 ){ head = head.getltree(); flag = 1; }else if( head.getrtree() != null && flag != 0 ){ if(head.getltree() == null){//因為左邊為空而返回 system.out.println( "<-1--中序遍歷--->" + head.getcode()); } head = head.getrtree(); choose = 1; }else if( flag == 0 && choose == 0 && head == star){ break; }else{ int area = 0;//判斷哪邊回來 flag = 1; choose = 1; if(head == head.getfronttree().getrtree()){ area = 1;//右邊回來 flag = 0; choose = 0; } if(head == head.getfronttree().getltree()){ area = 2;//左邊回來 choose = 0; flag = 1; } if( head.getltree() == null && head.getrtree() == null ){//因為左邊為空而返回 system.out.println( "<-2--中序遍歷--->" + head.getcode()); } head = head.getfronttree(); if( area == 2){//因為左邊訪問完返回 system.out.println( "<-3--中序遍歷--->" + head.getcode()); } system.out.println("獲得 父母" + head.getcode()); system.out.println( "\n\n\n" ); } } } /* * 非遞歸 后續遍歷 */ public void bottom_traverse(tree head){ tree star = head;//退出標記 int choose = 1; //左 int flag = 1; //右 while(true){ if( head.getltree() != null && choose != 0 ){ head = head.getltree(); flag = 1; }else if( head.getrtree() != null && flag != 0 ){ head = head.getrtree(); choose = 1; }else if( flag == 0 && choose == 0 && head == star){ break; }else{ int area = 0;//判斷哪邊回來 flag = 1; choose = 1; if(head == head.getfronttree().getrtree()){ area = 1;//右邊回來 flag = 0; choose = 0; } if(head == head.getfronttree().getltree()){ choose = 0; flag = 1; } if(head.getrtree() == null){//因為右邊為空而返回 system.out.println( "<-1--后序遍歷--->" + head.getcode()); } head = head.getfronttree(); if( area == 1){ system.out.println( "<-2--后序遍歷--->" + head.getcode()); } system.out.println("獲得 父母" + head.getcode()); system.out.println( "\n\n\n" ); } } }} |
2. tree 類實現：
|
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
|
public class tree { private int code = -1; private tree fonttree; private tree ltree; private tree rtree; tree(){ this.code = -1; this.ltree = null; this.rtree = null; } /* * 樹內容查看方法： */ public void setcode(int code){//設置編號 this.code = code; } public int getcode(){ //獲取編號 return this.code; } /* * 設置父母指針： */ public void setfronttree(tree front){ this.fonttree = front; } public tree getfronttree(){ system.out.println("獲得 父母"); return this.fonttree; } /* * 設置左子女： */ public void setltree(tree ltree){ this.ltree = ltree; } public tree getltree(){ system.out.println("獲得左子樹"); return this.ltree; } /* * 設置右子女： */ public void setrtree(tree rtree){ this.rtree = rtree; } public tree getrtree(){ system.out.println("獲得右子樹"); return this.rtree; }} |
3. 主函數測試：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class mainactivity { scanner sc = new scanner(system.in); public static void main(string[] args) { tree head = new tree(); tree_link link_1st = new tree_link(); head = link_1st.link_build(head); system.out.println("build succeed !"); system.out.println("\n二叉樹高度-->" + link_1st.getsave()); link_1st.output(head); system.out.println("output over !"); system.out.println("\n\n<----------------前------------------>\n前序訪問根："); link_1st.front_traverse(head); system.out.println("\n\n<----------------中------------------>\n中序訪問根："); link_1st.center_traverse(head); system.out.println("\n\n<----------------后------------------>\n后序訪問根："); link_1st.bottom_traverse(head); system.out.println("\n\n\n\ntext over !\n\n\n"); }} |
希望本文所述對大家java程序設計有所幫助。
原文鏈接：https://blog.csdn.net/qq_43377749/article/details/83475907
