图的广度优先搜索算法需使用的辅助数据结构为？

以二叉树的深度与广度优先遍历为例最合适不过了！！！

二叉树的遍历

它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

二叉树的遍历是指按照一定的次序访问树中所有结点，并且每个结点只被访问一次的过程。通常有四种遍历方式：

深度优先：（前序、中序、后序）

树的深度优先遍历，因为没有parent指针，所有非递归形式一定要借助栈；相反，如果二叉树的节点有parent指针，那么就不需要栈了。

1、前序遍历 （根-左-右）10,6,4,8,14,12,16

思路：

先让根进栈。只要栈不为空，就可以弹栈。每次弹出一个节点，要把它的左右节点进栈（右节点先进栈，因为栈是先进后出的）。

用途：拷贝树；计算前缀表达式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// 2、递归方法前序遍历（根-左-右）
// 虽然递归遍历简单和好理解，但是面对海量数据的时候，由于递归算法需要创建很多对象，需要占用大量内存，使得空间复杂度极大，也容易造成堆栈的溢出，因此递归算法面对海量数据时还是有非常致命的缺陷

import java.util.List;
import java.util.LinkedList;
class Solution {
    List<Integer> res = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null)
            return res;
        else{
            res.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return res;
    }
}

// 2.1 非递归方法前序遍历（根-左-右）
import java.util.List;
import java.util.Stack;
import java.util.LinkedList;
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null)
            return res;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while(! s.isEmpty()){
            TreeNode temp = s.pop();
            res.add(temp.val);
            if(temp.right != null)
                s.push(temp.right);
            if(temp.left != null)
                s.push(temp.left);
        }
        return res;
    }
}

2、中序遍历 （左-根-右）4,6,8,10,12,14,16

思路：

对于中序遍历来说，非递归的算法比递归算法的效率要高的多。中序遍历算法的实现的过程如下：

(1)初始化栈，根结点进栈；

(2)若栈非空，则栈顶结点的左孩子结点相继进栈，直到null(到叶子结点时)依次退栈并检测当前结点有无右孩子。

(3)重复执行(2)，直至栈为空。

用途：BST（二叉搜索树）的中序遍历以非降序方式输出节点

// 3、递归方法中序遍历（左-根-右）
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.List;
import java.util.LinkedList;
class Solution {
    List<Integer> res = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null)
            return res;
        else{
            inorderTraversal(root.left);
            res.add(root.val);
            inorderTraversal(root.right);
        }
        return res;
    }
}

// 3.1 非递归方法中序遍历（左-根-右）
import java.util.List;
import java.util.Stack;
import java.util.LinkedList;
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null)
            return res;
        Stack<TreeNode> s = new Stack<>();
        TreeNode temp = root;
        while(temp != null || !s.isEmpty()){
            while(temp != null){
                s.push(temp);
                temp = temp.left;
            }
            temp = s.pop();
            res.add(temp.val);
            temp = temp.right;
        }
        return res;
    }
}

3、后序遍历 （左-右-根）4,8,6,12,16,14,10

思路：

相当于前序遍历改变一下。由根-左-右变为根-右-左，再reverse一下，这里使用头插法，避免reverse的操作，同时使用LinkedList避免ArrayList的自动扩容，影响性能。

用途：删除树；计算后缀表达式

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// 4、递归方法后序遍历（左-右-根）
import java.util.List;
import java.util.LinkedList;
class Solution {
    List<Integer> res = new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return res;
        else{
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            res.add(root.val);
        }
        return res;
    }
}

// 4.1 非递归方法后序遍历（左-右-根）

import java.util.List;
import java.util.Stack;
import java.util.LinkedList;
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null)
            return res;
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while(!s.isEmpty()){
            TreeNode temp = s.pop();
            res.add(0, temp.val);
            if(temp.left != null)
                s.push(temp.left);
            if(temp.right != null)
                s.push(temp.right);
        }
        return res;
    }
}

广度优先：（层序）

• 层序遍历 10 6 14 4 8 12 16

无论是树，还是图的广度优先遍历（BFS），都要使用先进先出的队列结构。

层序遍历步骤：

1. 创建队列
2. tempnode = root
3. 队列不为空时，执行循环体
4. a）每轮以一层为单位
5. b) 将tempnode的左右孩子入队（先左后右），队尾入队
6. c) 出队（先进先出，满足层序遍历的要求），队头出队

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

 // 非递归解法
import java.util.List;
import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        if(root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> level = new LinkedList<>();
            int cnt = queue.size();// 当前队列的大小代表当层的结点个数
            for(int i = 0; i < cnt; i++){
                TreeNode temp = queue.poll();
                level.add(temp.val);
                if(temp.left != null)
                    queue.offer(temp.left);
                if(temp.right != null)
                    queue.offer(temp.right);
            }
            res.add(level);
        }
        return res;
    }
}

// 递归解法
import java.util.List;
import java.util.LinkedList;
class Solution {
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root != null)
            addData(root, 0);
        return res;
    }
    public void addData(TreeNode root, int depth){
        if(res.size() <= depth)
            res.add(new LinkedList<Integer>());
        res.get(depth).add(root.val);
        if(root.left != null)
            addData(root.left, depth + 1);
        if(root.right != null)
            addData(root.right, depth + 1);
    }
}

二叉树的遍历时间复杂度，无论递归与否，方式与否，都是O(n)。这是因为每个算法都要遍历每个节点仅仅一次。

广度优先用队列，深度优先用栈。

广度优先用到辅助队列，深度优先遍历用到辅助栈