数据结构专题：2.二叉树的遍历，深度优先，广度优先

1.先序遍历,非递归（利用stack）

public static void queryBtree(Node root){
  LinkedList<Node> stack = new LinkedList<Node>();
  stack.push(root);
  while(!stack.isEmpty()){
  Node currentNode = stack.pop();
  System.out.print(currentNode.value+" ");
  if(currentNode.right!=null){
  stack.push(currentNode.right);
  if(currentNode.left!=null){
  stack.push(currentNode.left);
  }
  }
}

2.中序遍历，非递归

public void queryBtree(Node<E> root) {
        LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
        Node currentNode = root;
        while (!stack.isEmpty()||currentNode!=null) {
            while(currentNode!=null){
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.pop();
            System.out.print(currentNode.value + " ");
            currentNode = currentNode.right;

        }
    }

3.广度优先

public void queryBtree(Node<E> root) {
        LinkedList<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> currentNode = queue.poll();
            System.out.print(currentNode.value+" ");
            if(currentNode.left!=null){
                queue.offer(currentNode.left);
            }
            if(currentNode.right!=null){
                queue.offer(currentNode.right);
            }
        }
    }

深度利用栈，广度利用queue