构造

//节点 public class Node { public int value; //数据 public Node left; //左节点 public Node right; //右节点 //构造函数 Node(int i){ value = https://www.it610.com/article/i; left=null; right=null; } }

二叉树的构造。
先要有一棵树，才能遍历一棵树。

static void preSet(Node node,Node[] nodes,int i){ if(i*2+1 < nodes.length) { node.left = nodes[i * 2+1]; } if(i*2+2 < nodes.length){ node.right = nodes[i*2+2]; } }

Node[] nodes = new Node[13]; for(int i =0 ; i<13; i++) { Node node = new Node(i); nodes[i] = node; } for(int i=0; i<13; i++){ preSet(nodes[i],nodes,i); }

首先构造一颗简单的完全二叉树


文章图片
Paste_Image.png 删去一些节点：

nodes[2].right=null; nodes[3].left=null; nodes[4].right=null; nodes[5].left=null;

文章图片
Paste_Image.png 生成了一棵树，开始遍历吧。

遍历

文章图片
Paste_Image.png 递归实现

• 前序遍历 => ABC

static void preTravel(Node node){ if(node==null ){ return; } System.out.print(node.value + ","); preTravel(node.left); preTravel(node.right); }

• 中序遍历 =>BAC

static void preTravel(Node node){ if(node==null ){ return; } preTravel(node.left); System.out.print(node.value + ","); preTravel(node.right); }

• 后续遍历 =>BCA

static void preTravel(Node node){ if(node==null ){ return; } preTravel(node.left); preTravel(node.right); System.out.print(node.value + ","); }

非递归实现 非递归实现，这里我根据网上的思路，用到了栈. (废话连篇) 其实不用栈也可以，毕竟看到了这个栈我是用ArrayList写的，所以只要用到栈的这种思路就行了，不一定一定要写一个栈。但是确实栈很方便...
一个简单的栈：

public class Stack { int current=0; private ArrayList nodes = new ArrayList(); boolean isEmpty(){ if(0==current){ return true; } return false; } void push(Node node){ if(node==null){ return; } nodes.add(node); current++; } Node pop() throws Exception{ if(isEmpty()){ throw new Exception(); } current--; return nodes.remove(current); } }

前序遍历

实现1：

static void preTraverse(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); s.push(node); while (!s.isEmpty()){ Node item = s.pop(); System.out.print(item.value + ","); s.push(item.right); s.push(item.left); } System.out.println(); }

这个实现方法不够好吧。
缺点分析：每次都要先push再pop。可不可以必须push才push呢？
实现2：
直接将node=node.left ,而不是每次先push再pop 出来。

static void preTraverse2(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while (node !=null ||!s.isEmpty()){ if(node!=null) { System.out.print(node.value + ","); s.push(node.right); node = node.left; }else { node = s.pop(); } } System.out.println(); }

进一步优化：
实现3：
优化的地方是，检查条件，内嵌了一个while( node != null ),使得不必每次只需检查node != null的时候还检查了！s.isEmpty()
但是多了个异常捕获。因为这样可能，栈为空的时候还向栈中取元素。

static void preTraverse3(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); try { while (node != null || !s.isEmpty()) { while (node != null) { System.out.print(node.value + ","); s.push(node.right); node = node.left; } node = s.pop(); } }catch (Exception e){ ; } System.out.println(); }

进一步优化：
发现，
1.只有在pop时候，在需要检查栈是否空
2.初始化的时候栈为空，
3.内嵌了一个while(node！=null)，只有在node为空的时候，才会去栈中获取元素，如果获取不到元素，那么外围的while(node！=null)检查条件依然有效.
实现4：

static void preTraverse4(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while (node != null ) { while (node != null) { System.out.print(node.value + ","); s.push(node.right); node = node.left; } if( !s.isEmpty()) { node = s.pop(); } } System.out.println(); }

进一步优化：
实现5：
额，好吧，节省了一个的node！=null的检查而已...

static void preTraverse5(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while (node != null ) { System.out.print(node.value + ","); s.push(node.right); node = node.left; while (node != null) { System.out.print(node.value + ","); s.push(node.right); node = node.left; } if( !s.isEmpty()) { node = s.pop(); } } System.out.println(); }

好了，我是到此结束了。
其他的书写思路一样，快速看，就直接溜到结尾的实现中。（多么贴心的boy！）

中序遍历

实现1：

static void InOrderTraverse(Node node)throws Exception{ if(node==null){return; } Stack s=new Stack(); s.push(node); while(!s.isEmpty()){ node = s.pop(); //如果左节点不存在 if(node.left!=null){ s.push(node); s.push(node.left); }else if(node.right!=null){//如果右节点不存在 System.out.print(node.value+","); s.push(node.right); }else{//其他的情况，那就是没有节点嘛 System.out.print(node.value+","); node = s.pop(); while(node.right==null){ System.out.print(node.value+","); if(!s.isEmpty()) { node = s.pop(); //获取父亲节点 }else{ return; } } System.out.print(node.value+","); s.push(node.right); } } }

这个代码看起来就很头大，本人写的，自己都看不下去..也是调试后写出来的。不管了。优化。
实现2：
主要是不要非得将节点放入栈，再拿出这种浪费效率的工作。而是直接node=node.left; node=node.right;

//BACstatic void InOrderTraverse3(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ if(node.left!=null){//如果左节点不为空 s.push(node); node = node.left; }else if(node.right!=null){//如果右节点不为空 System.out.print(node.value + ","); node =node.right; }else {//否则就是都是空 System.out.print(node.value + ","); node = s.pop(); //获取父亲节点 while(node.right==null){ System.out.print(node.value + ","); if(!s.isEmpty()) { node = s.pop(); }else{ return; } } System.out.print(node.value + ","); node=node.right; } } }

实现3：
这里其实并没有优化，而是合并了下代码。

static void InOrderTraverse4(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ if(node.left!=null){ s.push(node); node = node.left; }else if(node.right!=null){ System.out.print(node.value + ","); node =node.right; }else { while (node.right == null) { System.out.print(node.value + ","); if(!s.isEmpty()) { node = s.pop(); }else{ return; } } System.out.print(node.value + ","); node=node.right; } } }

实现4：
发现其实第二个else if 中的操作了，else中的操作其实是一致的，可以合并：

static void InOrderTraverse6(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ while(node.left!=null){ s.push(node); node = node.left; } while(node.right == null){ System.out.print(node.value + ","); if(!s.isEmpty()) { node = s.pop(); }else{ return; } } System.out.print(node.value + ","); node = node.right; } }

实现5：
其实是把后半部分的代码移动了一下而已...

static void InOrderTraverse7(Node node)throws Exception{ if(node==null){return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ while(node.left!=null){ s.push(node); node = node.left; } System.out.print(node.value + ","); node=node.right; while(node ==null){ if(!s.isEmpty()) { node = s.pop(); System.out.print(node.value + ","); node=node.right; }else{return; } } } }

实现6：
又是换了下代码的位置而已，其实是想少一个while，想利用外面的while，本来就要检查!s.isEmpty。

static void InOrderTraverse8(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ if(node==null){ node=s.pop(); System.out.print(node.value + ","); node=node.right; }else { while (node.left != null) { s.push(node); node = node.left; } System.out.print(node.value + ","); node = node.right; } } }

实现7：
这个优化，有点明显的，额。
1.上面步骤中，else部分，的下半部分，其实操作和if的下半部分一样
2.else中上面是push。if中有个pop

static void InOrderTraverse10(Node node)throws Exception{ if(node==null){return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ if(node==null){ node=s.pop(); System.out.print(node.value + ","); node=node.right; }else{ while (node.left != null) { s.push(node); node = node.left; } s.push(node); } } }

实现8：
无论如何s.push(node)这个操作都会被执行。所以：

static void InOrderTraverse9(Node node)throws Exception{ if(node==null){ return; } Stack s=new Stack(); while(node!=null || !s.isEmpty()){ if(node==null){ node=s.pop(); System.out.print(node.value + ","); node=node.right; }else{ s.push(node); node = node.left; } } }

实现9：
网友的实现，我就是因为网友这个刺激的呀，所以一步步实现优化。
这里又把检测条件缩小了一下。

static void InOrderTraverse2(Node node)throws Exception{ if(node==null){return; } Stack s=new Stack(); while( node!=null || !s.isEmpty()){ while(node!=null){ s.push(node); node = node.left; } node = s.pop(); System.out.print(node.value+","); node=node.right; } }

后序遍历

实现1：

static void postTraverse(Node node)throws Exception{ if(node==null){return; } Stack s = new Stack(); s.push(node); while (!s.isEmpty()){ node = s.pop(); if(node.left==null && node.right==null){ System.out.print(node.value + ","); Node node1 =s.pop(); while(node1.left == node || node1.right == node){ System.out.print(node1.value+","); node = node1; try{ node1=s.pop(); }catch (Exception e){ return; } } s.push(node1); }else { s.push(node); s.push(node.right); s.push(node.left); } } }

实现2：
主要是
1.简化了pop和push操作，将操作变简单

static void postTraverse2(Node node)throws Exception{ if(node==null){return; } Stack s = new Stack(); try { while (node != null || !s.isEmpty()) { if(node==null){ node =s.pop(); } if (node.left == null && node.right == null) { System.out.print(node.value + ","); Node node1 = s.pop(); //获取父节点 while (node1.left == node || node1.right == node) {//检查是不是父节点 System.out.print(node1.value + ","); node = node1; node1 = s.pop(); } node=node1; } else { s.push(node); s.push(node.right); node = node.left; } } }catch (Exception e){ return; } System.out.println(); }

实现3：
【二叉树的遍历】并没有实质性的优化...

static void postTraverse3(Node node)throws Exception{ if(node==null){return; } Stack s = new Stack(); try { while (node != null || !s.isEmpty()) { if(node==null){ node =s.pop(); } if (node.left == null && node.right == null) { System.out.print(node.value + ","); Node tmp=node; node = s.pop(); //获取父节点 while (node.left == tmp || node.right == tmp) {//检查是不是父节点 System.out.print(node.value + ","); tmp = node; node = s.pop(); } } else { s.push(node); s.push(node.right); node = node.left; } } }catch (Exception e){ return; } }

实现4：

static void postTraverse4(Node node)throws Exception{ if(node==null){ return; } Stack s = new Stack(); try { while (node != null || !s.isEmpty()) { if (node.left == null && node.right == null) { Node tmp; do { System.out.print(node.value + ","); tmp = node; node = s.pop(); //获取父节点 }while (node.left == tmp || node.right == tmp); //检查是不是父节点 }else { s.push(node); s.push(node.right); node = node.left; if(node==null){ node =s.pop(); } } } }catch (Exception e){ return; } }

实现5：

网友的思路是： 设置标志位，如果读取过一次就置1.不然，就设置0. 就是Stack中他添加了一个tag数组，用于设置其标志位。 void postorder_dev(bintree t){ seqstack s; s.top = -1; if(!t){ printf("the tree is empty!\n"); }else{ while(t || s.top != -1){//栈空了的同时t也为空。 while(t){ push(&s,t); s.tag[s.top] = 0; //设置访问标记，0为第一次访问，1为第二次访问 t= t->lchild; } if(s.tag[s.top] == 0){//第一次访问时，转向同层右结点 t= s.data[s.top]; //左走到底时t是为空的，必须有这步！ s.tag[s.top]=1; t=t->rchild; }else { while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点，退出循环时并没有pop所以为其左子结点 t = pop(&s); printf("%c ",t->data); } t = NULL; //必须将t置空。跳过向左走，直接向右走 } } } }

层级遍历

static void levelTravel(Node node){ if(node==null){ return; } ArrayList nodes= new ArrayList(); nodes.add(node); while(!nodes.isEmpty()){ Node item = nodes.remove(0); if(item==null){ continue; } System.out.println(item.value); nodes.add(item.left); nodes.add(item.right); } }

推荐阅读

• 

  出国翻译官如何进行拍照翻译？出国翻译官进行拍照翻译的方法
• 

  打疫苗还要做核酸检测吗
• 

  澳门行
• 

  华硕的主板怎么调u盘启动
• 

  佳能ef-m55-200镜头 佳能efm55-200镜头评测
• 

  php数据库类 php中数据库怎么设计
• 

  z25
• 

  三令五申的历史典故 有三令五申的典故是谁
• 

  【图像美化神器】quickshot快速入门教程
• 

  C#多态的三种实现方式(小结)
• 

  6.9
• 

  屈原清正廉洁的故事
• 

  开学了，与其逼迫孩子学习，不如帮他改掉这几个坏习惯
• 

  牛奶炖鲤鱼养颜补虚 推荐4款滋补养颜菜谱
• 

  树莓派|树莓派安装成功后，搜索不到自己的WIFI
• 

  佳能6d2手柄 佳能7d2手柄
• 

  空调不制冷有味道怎么办？
• 

  煲汤的诀窍及攻略
• 

  澳柯玛冰箱故障码ef
• 

  顺丰快递员真实感受 顺丰快递员真实收入

• 热闹中的孤独
• JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
• 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
• 一个人的旅行，三亚
• 布丽吉特，人生绝对的赢家
• 慢慢的美丽
• 尽力
• 一个小故事，我的思考。
• 家乡的那条小河
• 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量