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 }
