二叉树的遍历(java)

对于二叉树的遍历，我用的是队列去进行存放树中的数据，基于队列的先进先出的思想，能够很好的实现二叉树的遍历

前序遍历是先从根节点开始向左节点遍历，直到最左节点也走到后就开始从最左节点的右节点开始遍历

 前序遍历结果：EBADCGFH

 private void preErgodic(Node x,Queue keys){
        if (x == null){
            return;
        }
        keys.enqueue(x.key);
        if (x.left != null){
            preErgodic(x.left,keys);
        }
        if (x.right != null){
            preErgodic(x.right,keys);
        }
    }

中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。可以看作是从左到右，上面的节点垂直下来一排

  中序遍历结果：ABCDEFGH

private void midErgodic(Node x,Queue keys){
        if (x == null){
            return;
        }
        if (x.left != null){
            midErgodic(x.left,keys);
        }
        keys.enqueue(x.key);
        if (x.right != null){
            midErgodic(x.right,keys);
        }
    }

后序遍历是先左后右再根，先把左子树从下往上遍历完再把右子树从下往上遍历，然后访问根节点

后序遍历结果：ACDBFHGE

private void afterErgodic(Node x,Queue keys){
        if (x == null){
            return;
        }
        if (x.left != null){
            afterErgodic(x.left,keys);
        }
        if (x.right != null){
            afterErgodic(x.right,keys);
        }
        keys.enqueue(x.key);
    }

层序遍历就比较简单好理解了，从根节点开始从上往下从左往右每一层遍历

 层序遍历结果：EBGADFHC

 public Queue layerErgodic(){
        Queue keys = new Queue<>();
        Queue nodes = new Queue<>();
        nodes.enqueue(root);
        while (!nodes.isEmpty()){
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            if (n.left != null){
                nodes.enqueue(n.left);
            }
            if (n.right != null){
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }