黑马程序员技术交流社区

标题: java二叉树 [打印本页]

---

作者: 韩冬    时间: 2013-6-24 00:52
标题: java二叉树


求一个JAVA实现二叉树的具体代码过程。

---

作者: likairoudou    时间: 2013-6-24 17:13

1. import java.util.ArrayList;
   
2.   
   
3. //
   
4. 树的一个节点
   
5. 
   
6. class TreeNode {
   
7.   
   
8. 
   
9. 
   
10. 
    
11. 
    
12. Object _value = null; //
    
13. 他的值
    
14.   
    
15. 
    
16. 
    
17. 
    
18. 
    
19. TreeNode _parent = null; //
    
20. 他的父节点，根节点没有
    
21. PARENT
    
22. 
    
23. 
    
24. 
    
25. 
    
26. ArrayList _childList = new ArrayList(); //
    
27. 他的孩子节点
    
28. 
    
29.   
    
30. 
    
31. 
    
32. 
    
33. 
    
34. public TreeNode( Object value, TreeNode parent ){
    
35. 
    
36. 
    
37. 
    
38. 
    
39. 
    
40. 
    
41. 
    
42. 
    
43. this._parent = parent;
    
44. 
    
45. 
    
46. 
    
47. 
    
48. 
    
49. 
    
50. 
    
51. 
    
52. this._value = value;
    
53. 
    
54. 
    
55. 
    
56. 
    
57. }
    
58.   
    
59. 
    
60. 
    
61. 
    
62. 
    
63. public TreeNode getParent(){
    
64. 
    
65. 
    
66. 
    
67. 
    
68. 
    
69. 
    
70. 
    
71. 
    
72. return _parent;
    
73. 
    
74. 
    
75. 
    
76. 
    
77. }
    
78.   
    
79. 
    
80. 
    
81. 
    
82. 
    
83. public String toString() {  
    
84. 
    
85. 
    
86. 
    
87. 
    
88. 
    
89. 
    
90. 
    
91. 
    
92. return _value.toString();
    
93. 
    
94. 
    
95. 
    
96. 
    
97. }
    
98. }
    
99.   
    
100. public class Tree {
     
101.   
     
102. 
     
103. 
     
104. 
     
105. 
     
106. //
     
107. 给出宽度优先遍历的值数组，构建出一棵多叉树
     
108. 
     
109. 
     
110. 
     
111. 
     
112. 
     
113. // null
     
114. 值表示一个层次的结束
     
115.   
     
116. 
     
117. 
     
118. 
     
119. 
     
120. // "|"
     
121. 表示一个层次中一个父亲节点的孩子输入结束
     
122. 
     
123. 
     
124. 
     
125. 
     
126. 
     
127. //
     
128. 如：给定下面的值数组：
     
129.   
     
130. 
     
131. 
     
132. 
     
133. 
     
134. // { "root", null, "left", "right", null }  
     
135. 
     
136. 
     
137. 
     
138. 
     
139. //
     
140. 则构建出一个根节点，带有两个孩子
     
141. ("left","right")
     
142. 的树
     
143. 
     
144. 
     
145. 
     
146. 
     
147. 
     
148. public Tree( Object[] values ){
     
149. 
     
150. 
     
151. 
     
152. 
     
153. 
     
154. 
     
155. 
     
156. 
     
157. //
     
158. 创建根
     
159.   
     
160. 
     
161. 
     
162. 
     
163. 
     
164. 
     
165. 
     
166. 
     
167. 
     
168. _root = new TreeNode( values[0], null );
     
169.   
     
170. 
     
171. 
     
172. 
     
173. 
     
174. 
     
175. 
     
176. 
     
177. 
     
178. //
     
179. 创建下面的子节点
     
180.   
     
181. 
     
182. 
     
183. 
     
184. 
     
185. 
     
186. 
     
187. 
     
188. 
     
189. TreeNode currentParent = _root; //
     
190. 用于待创建节点的父亲
     
191. 
     
192. 
     
193. 
     
194. 
     
195. 
     
196. 
     
197. 
     
198. 
     
199. 
     
200. //TreeNode nextParent = null;  
     
201. 
     
202. 
     
203. 
     
204. 
     
205. 
     
206. 
     
207. 
     
208. 
     
209. int currentChildIndex = 0; //
     
210. 表示
     
211. 
     
212. currentParent
     
213. 是他的父亲的第几个
     
214. 儿子
     
215.   
     
216. 
     
217. 
     
218. 
     
219. 
     
220. 
     
221. 
     
222. 
     
223. 
     
224. //TreeNode lastNode = null; //
     
225. 最后一个创建出来的
     
226. TreeNode
     
227. ，用于
     
228. 找到他的父亲
     

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2