java-二叉树遍历
1，完全二叉树-建树，先建简单的树，用简单的树学习各种遍历
2，根据先中序建树，根据中后序建树
1 //先简单建树-按完全二叉树节点插入顺序建树，即层序遍历。2
3 /**二叉树：每个节点最多两个孩子节点（计划生育-最多生二胎）；
4 * 完全二叉树（遏制人口老龄化：必须生两胎，否则不准后代传宗接代）：
5 * 根节点（爷爷）先生，生不满两胎接着生，爷爷生完，老大（左爸爸）生，
6 * 生不满二胎，爷爷的小儿子不准生，。。。依次类推。
7 * */
8
9 /**按层间遍历顺序加入节点
10 层序遍历用队列，根节点入队，
11 执行循环，当队列不为空{对首X出队，若X左孩子非空，入队，右孩子非空入队}
12 */
13
14 /**层序遍历（用队列先进先出性能实①现先访问根节点（第一层）
15 ②再依次访问根节点的左右孩子节点（第二层）
16 ③再依次访问根节点左右孩子节点的左右孙子节点(第三层)，
17 ④.....
18 */
19
20 /**？
21 * 功能
22 * ①，建树--体会完全二叉树，添加节点过程（先建简单的，主要还是体会各种遍历）
23 * ②，4种遍历，7种方法，前、中、后序递归遍历，前、中、后非递归遍历，层序遍历。
24 * ③，删树，
25 * ④，求树高
26 * ⑤，树状打印
27 * ⑥，
28 */
29
30 import java.util.Arrays;
31 import java.util.LinkedList;
32 import java.util.Queue;
33 import java.util.Stack;
34
35 public class Easy_BiTree {
36 //内部Node类
37 public class Node {
38 private int data=Integer.MAX_VALUE;
39 private Node lchild=null;
40 private Node rchild=null;
41
42 public Node(){}
43 public Node(int data){
44 this.data=data;
45 }
46 }
47
48 private Node root=null;
49 private int size=0;
50 public Easy_BiTree(){}
51
52 //添加节点
53 public void addNode(Node root,int data){
54 //根节点
55 if(size==0){
56 this.root=new Node(data);
57 size++;
58 }else{
59 Node newNode=new Node(data);
60
61 // 添加节点用层序遍历方法目的不是为了遍历每一个节点,而是按层次顺序找到第一个孩子不满（没生二胎）的节点
62 // 当遇到孩子节点没满的Node,添加节点-退出；
63 Queue<Node> queue=new LinkedList<>();
64 queue.add(root);
65 while(!queue.isEmpty()){
66 Node curroot=queue.poll();
67 if(curroot.lchild!=null)
68 queue.add(curroot.lchild);
69 else{
70 curroot.lchild=newNode;
71 size++;
72 return;
73 }
74 if(curroot.rchild!=null)
75 queue.add(curroot.rchild);
76 else{
77 curroot.rchild=newNode;
78 size++;
79 return;
80 }
81 }
82 }
83 }
84
85 //遍历-前序非递归，
86
87 /**
88 * ①顺着根节点的左孩子一路到底，一边输出一边入栈，
89 * ②到底后，判断栈顶有没有右子树，有以右子节点为根节点重复①，没有则出栈，
90 */
91 public void preOrder(Node root){
92 if(size==0)
93 System.out.println("树空无遍历");
94 else{
95 System.out.print("树前序非递归： ");
96 Stack<Node> stack=new Stack<>();
97 while(root!=null||!stack.isEmpty()){
98 while(root!=null){
99 System.out.print(root.data+" ");
100 stack.add(root);
101 root=root.lchild;
102 }
103 if(!stack.isEmpty()){
104 root=stack.pop();
105 root=root.rchild;
106 }
107 }
108 System.out.println();
109 }
110 }
111 //遍历-中序非递归，
112 public void inOrder(Node root){
113 if(size==0)
114 System.out.println("树空，无遍历");
115 else {
116 System.out.print("树中序非递归： ");
117 Stack<Node> stack=new Stack<>();
118 while(root!=null||!stack.isEmpty()){
119 while(root!=null){
120 stack.add(root);
121 root=root.lchild;
122 }
123 if(!stack.isEmpty()){
124 root=stack.pop();
125 System.out.print(root.data+" ");
126 root=root.rchild;
127 }
128 }
129 System.out.println();
130 }
131 }
132 //遍历-后序非递归，
133 /**
134 *①顺着根节点的左孩子一路到底，入栈，
135 * ②到底后，判断栈顶有没有右子树，没有出栈，输出
136 * ③有右子节点，右子节点遍历之前不能出栈，preNode,即标识右子节点有没有遍历，
137 * 以右子节点为根节点重复①，②③
138 */
139 public void postOrder(Node root){
140 if(size==0)
141 System.out.println("树空，无遍历");
142 else {
143 System.out.print("树后序非递归： ");
144 Stack<Node> stack=new Stack<>();
145 while(root!=null||!stack.isEmpty()){
146 while(root!=null){
147 stack.push(root);
148 root=root.lchild;
149 }
150 boolean tag=true;
151 Node preNode=null;
152 while(!stack.isEmpty()&&tag==true){
153 root=stack.peek();
154 if(root.rchild==preNode){
155 root=stack.pop();
156 System.out.print(root.data+" ");
157 if(stack.isEmpty()){
158 System.out.println();
159 return;
160 }
161 else
162 preNode=root;
163 }else{
164 root=root.rchild;
165 tag=false;
166 }
167 }
168 }
169 System.out.println();
170 }
171 }
172
173 /**
174 * 额。。递归写起来是很简单，我也说不好原理，233
175 */
176 //遍历-前序递归，
177 public void preOrderRec(Node root){
178 if(root==null)
179 return;
180 else {
181 System.out.print(root.data+" ");
182 preOrderRec(root.lchild);
183 preOrderRec(root.rchild);
184 }
185 }
186 //遍历-中序递归，
187 public void inOrderRec(Node root){
188 if(root==null)
189 return;
190 else{
191 inOrderRec(root.lchild);
192 System.out.print(root.data+" ");
193 inOrderRec(root.rchild);
194 }
195 }
196 //遍历-后序递归，
197 public void postOrderRec(Node root){
198 if(root==null)
199 return;
200 else{
201 postOrderRec(root.lchild);
202 postOrderRec(root.rchild);
203 System.out.print(root.data+" ");
204 }
205 }
206
207
208
209 //遍历，-层间遍历
210 public void levelOrder(Node root){
211 if(this.size==0)
212 System.out.println("空树，无法遍历");
213 else{
214 System.out.println("树层间遍历：");
215 Queue<Node> queue=new LinkedList<>();
216 queue.add(root);
217 while(!queue.isEmpty()){
218 Node curroot=queue.poll();
219 System.out.print(curroot.data+" ");
220 if(curroot.lchild!=null)
221 queue.add(curroot.lchild);
222 if(curroot.rchild!=null)
223 queue.add(curroot.rchild);
224 }
225 System.out.println();
226 }
227 }
228
229 //删树
230 //java有内存回收机制，只要把根节点状态，换成空树根节点状态即可；
231 //C++也是类似遍历一遍，把遍历到的每一个节点free;
232
233 //呃。。。。我猜的，哈哈哈哈哈哈哈哈
234 public void deleteTree(){
235 this.root=null;
236 size=0;
237 }
238
239 /**
240 * 树高-递归和非递归方法
241 * 完全二叉树，节点和高有方程，log(size)向下取整+1
242 * 这里用非特殊二叉树求树高，
243 */
244
245 //转载：https://blog.csdn.net/shijie97/article/details/79775399
246 /**非递归-队列，
247 * 根节点入队，出队，添加第二层，添加完后记录队size(0/1/2)，然后将（0/1/2）个出队，将他们的孩子入队，记录每一层
248 * 孩子数，遍历完，即可知道层数
249 */
250 public int treeHeight(Node root){
251 if(root==null)
252 return 0;
253 else if(size==1)
254 return 1;
255 else{
256 Queue<Node> queue=new LinkedList<>();
257 queue.add(root);
258 int height=0;
259 //记录每层孩子个数,root入队长为1
260 int len=1;
261 while(!queue.isEmpty()){
262 int length=0;
263 for(int i=0;i<len;i++){
264 Node curroot=queue.poll();
265 if(curroot.lchild!=null){
266 queue.add(curroot.lchild);
267 length++;
268 }
269 if(curroot.rchild!=null){
270 queue.add(curroot.rchild);
271 length++;
272 }
273 }
274 len=length;
275 height++;
276 }
277 return height;
278 }
279 }
280 //递归
281 public int treeHeightRec(Node root){
282 if(root==null)
283 return 0;
284 else{
285 int a =treeHeightRec(root.lchild);
286 int b = treeHeightRec(root.rchild);
287 return (a>b)?(a+1):(b+1);
288 }
289 }
290
291 //树状打印
292 /**
293 * 思路：先确定树高h-最后一层2^(h-1)个数，好知道根节点放在哪里（预留空间保证根再中间）
294 * 设每个data三位数=space,元素之间空三位数，每行 (2^H+1)*3 个“ ”
295 * _数_数_数_数_数_ 每层2^(h-1)个数，2^(h-1)+1个space,最后一行长2^h+1个space
296 *
297 * 当层数多的时候稍乱，2333不想弄了，
298 */
299 public void printTree(Node root){
300 int H=treeHeight(root);
301 int h=H;
302 //System.out.println("树高："+H);
303 if(H==0)
304 System.out.println("树空,无打印");
305 else{
306 System.out.println("打印树：");
307 Queue<Node> queue=new LinkedList<>();
308 queue.add(root);
309 int height=1;
310 //记录每层孩子个数
311 int len=1;
312 while(h>0){
313 int length=0;
314 String space="";
315 for(int i=0;i<(((Math.pow(2,H)+1)*3)/(Math.pow(2,height)+1));i++)
316 space+=" ";
317 for(int i=0;i<len;i++){
318 Node curroot=queue.poll();
319 if(curroot.data==Integer.MAX_VALUE){
320 System.out.print(space);
321 }else
322 System.out.print(space+curroot.data);
323
324 if(curroot.lchild!=null){
325 queue.add(curroot.lchild);
326 }
327 else
328 queue.add(new Node());
329 length++;
330 if(curroot.rchild!=null){
331 queue.add(curroot.rchild);
332 }
333 else
334 queue.add(new Node());
335 length++;
336 }
337 System.out.println();
338 System.out.println();
339 len=length;
340 height++;
341 h--;
342 }
343 System.out.println();
344 }
345 }
346
347
348 /**
349 *
350 * 根据先序和中序创建二叉树
351 * 转载：https://www.cnblogs.com/tuyang1129/p/11647443.html
352 * ①先序的第一个元素为根节点，②找出这个根节点在中序中的位置x,xx左边是根节点的左子树，右边是右子树
353 * ③递归建树
354 *
355 */
356
357 public int getIndex(int data,int[] array){
358 int num =Integer.MAX_VALUE;
359 for(int i=0;i<array.length;i++){
360 if(array[i]==data)
361 num=i;
362 }
363 return num;
364 }
365
366 public Node preIn_BiTree(int[] pre,int[] in){
367 if(pre.length==0){
368 return null;
369 }else if(pre.length==1){
370 return new Node(pre[0]);
371 }
372 Node root=new Node(pre[0]);
373
374 int index=getIndex(pre[0],in);
375
376 //左子树
377 int[] preleft= Arrays.copyOfRange(pre,1,index+1);
378 int[] inleft=Arrays.copyOfRange(in,0,index);
379 root.lchild=preIn_BiTree(preleft,inleft);
380
381 //右子树
382 int[] preright=Arrays.copyOfRange(pre,index+1,pre.length);
383 int[] inright=Arrays.copyOfRange(in,index+1,in.length);
384 root.rchild=preIn_BiTree(preright,inright);
385
386 return root;
387
388 }
389
390 /**
391 * 根据中序-后续
392 * ①后序的第一个元素为根节点，②找出这个根节点在中序中的位置x,x左边是根节点的左子树，右边是右子树
393 * ③递归建树
394 */
395 public Node inPost_BiTree(int[] in,int[] post){
396 if(in.length==0){
397 return null;
398 }else if(in.length==1){
399 return new Node(in[0]);
400 }
401 Node root=new Node(post[post.length-1]);
402 int index=getIndex(post[post.length-1],in);
403
404 //左子树
405 int[] postleft= Arrays.copyOfRange(post,0,index);
406 int[] inleft=Arrays.copyOfRange(in,0,index);
407 root.lchild=inPost_BiTree(inleft,postleft);
408
409 //右子树
410 int[] postright=Arrays.copyOfRange(post,index,post.length-1);
411 int[] inright=Arrays.copyOfRange(in,index+1,in.length);
412 root.rchild=inPost_BiTree(inright,postright);
413
414 return root;
415
416 }
417
418
419
420
421 public static void main(String args[]) {
422 /**
423 * 完全二叉树的建立，与二叉树的遍历
424 */
425 Easy_BiTree t=new Easy_BiTree();
426 t.addNode(t.root,1);
427 t.addNode(t.root,2);
428 t.addNode(t.root,3);
429 t.addNode(t.root,4);
430 t.addNode(t.root,5);
431 t.addNode(t.root,6);
432 t.addNode(t.root,7);
433 t.addNode(t.root,8);
434 t.addNode(t.root,9);
435 t.addNode(t.root,10);
436 t.addNode(t.root,11);
437 t.addNode(t.root,12);
438 t.addNode(t.root,13);
439 t.addNode(t.root,14);
440 t.addNode(t.root,15);
441 t.addNode(t.root,16);
442 t.addNode(t.root,17);
443 t.addNode(t.root,18);
444 t.addNode(t.root,19);
445 t.addNode(t.root,20);
446 t.addNode(t.root,21);
447
448 t.levelOrder(t.root);
449 System.out.println("非递归求树高： "+t.treeHeight(t.root));
450 System.out.println("递归求树高： "+t.treeHeightRec(t.root));
451
452 t.printTree(t.root);
453
454 t.preOrder(t.root);
455 t.inOrder(t.root);
456 t.postOrder(t.root);
457
458 System.out.print("树前序递归遍历： ");
459 t.preOrderRec(t.root);
460 System.out.println();
461 System.out.print("树中序递归遍历： ");
462 t.inOrderRec(t.root);
463 System.out.println();
464 System.out.print("树后序递归遍历： ");
465 t.postOrderRec(t.root);
466 System.out.println();
467
468 t.deleteTree();
469 System.out.println("非递归求树高： "+t.treeHeight(t.root));
470
471
472 /**
473 * 其他建树方法
474 */
475 int[] pre={1,2,4,7,3,5,6};
476 int[] in={2,7,4,1,5,3,6};
477 int[] post={7,4,2,5,6,3,1};
478
479 int[] pre1={1,2,3,4,5,6,7};
480 int[] in1={2,4,6,7,5,3,1};
481 int[] post1={7,6,5,4,3,2,1};
482
483
484 System.out.println("pre={1,2,4,7,3,5,6}");
485 System.out.println("in={2,7,4,1,5,3,6}");
486 Easy_BiTree t2=new Easy_BiTree();
487 t2.root=t2.preIn_BiTree(pre,in);
488 t2.printTree(t2.root);
489
490 System.out.println("pre1={1,2,3,4,5,6,7}");
491 System.out.println("in1={2,4,6,7,5,3,1}");
492 Easy_BiTree t3=new Easy_BiTree();
493 t3.root=t3.preIn_BiTree(pre1,in1);
494 t3.printTree(t3.root);
495
496 System.out.println("in={2,7,4,1,5,3,6}");
497 System.out.println("post={7,4,2,5,6,3,1}");
498 Easy_BiTree t4=new Easy_BiTree();
499 t4.root=t4.inPost_BiTree(in,post);
500 t4.printTree(t4.root);
501
502 System.out.println("in1={2,7,4,1,5,3,6}");
503 System.out.println("post1={7,4,2,5,6,3,1}");
504 Easy_BiTree t5=new Easy_BiTree();
505 t5.root=t5.inPost_BiTree(in1,post1);
506 t5.printTree(t5.root);
507
508 }
509 }
View Code
以上是 java-二叉树遍历 的全部内容， 来源链接： utcz.com/z/390697.html
