利用双端队列 实现二叉树的非递归的中序遍历

双端队列：双向队列：支持插入删除元素的线性集合。
java官方文档推荐用deque实现栈（stack）。

pop(): 弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException
push(): 向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NPE，如果栈空间受到限制，则发生IllegalStateException

代码：

public void inOrderByStack(Node node) {System.out.println("中序非递归遍历");Deque stack=new LinkedList();//创建一个双端队列Node current =root;while (current!=null||!stack.isEmpty()){//栈非空while(current!=null){stack.push(current);//把current压zhancurrent=current.leftChild;//把current的左孩子节点赋值给它}if (!stack.isEmpty()) {current =(Node) stack.pop();//栈非空就出栈System.out.println(current.value);current=current.rightChild;//遍历右孩子}}}

二叉树图如下：

        root节点=Node1,把Node1的值赋值给current,current 值不为null

把current 值压栈，Node1的值压栈；Node4的值赋值给curent；

 stack.push(current);//把current压zhancurrent=current.leftChild;

   再判断4是否为null，把4的值压栈，current=null(Node4 )没有左孩子

判断为否定，跳出循环

stack非空，cuurrent =等于刚被压栈的Node4；输出Node4，并且把Node5的值赋值给current

再次回到第一个循环：

 while(current!=null){stack.push(current);//把current压zhancurrent=current.leftChild;//把current的左孩子节点赋值给它}

       Node5压栈，然后把null赋值给curent

再次判断不满足，此时current为Node5,输出5，再把Node5的右孩子赋值给current

经过while循环判断：

while (current!=null||!stack.isEmpty())

stack非空继续执行while 

把null值压栈，current=null的左孩子还是null

判断if还是非空，那么把Node1的值赋值给current并且输出1,

把1的右孩子赋值给current,不再赘述