java数据结构与算法之二叉树深度优先和广度优先遍历

本文主要是介绍java数据结构与算法之二叉树深度优先和广度优先遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、宽度优先遍历

算法流程：

宽度优先遍历使用 队列，先进先出。

1. 先将头节点压入队列中，进入while循环
2. 每循环一次就从队列中弹出一个元素，弹出就打印。
3. 将该弹出元素的左右孩子节点压入队列中（如果有的话），先压左孩子，再压右孩子。
4. 重复上面第 2 、3 步骤，直到队列为空
5. 当遍历完整棵树以后就完成了树的宽度优先遍历

代码如下：

/**
 * 二叉树宽度优先遍历
 * 宽度优先用队列
 */
public static void widthPriority(final TreeNode head) {
  if (head == null) {
    return;
  }
  final LinkedList<TreeNode> queue = new LinkedList<>();
  queue.add(head);

  while (!queue.isEmpty()) {
    // 从队列里弹出一个元素，弹出就打印
    final TreeNode node = queue.pop();
    System.out.println(node.data);
    // 左孩子压入队列（如果有）
    if (node.left != null) {
      queue.add(node.left);
    }
    // 右孩子压入队列（如果有）
    if (node.right != null) {
      queue.add(node.right);
    }
  }

}

二、深度优先遍历

二叉树的中序遍历其实就是树的深度优先遍历 !!!

方式一、自己用栈实现

/**
 * 二叉树深度优先遍历（中序遍历其实就是深度优先遍历）
 * 深度优先用栈实现
 */
public static void deepPriority(final TreeNode head) {
    if (head == null) {
        return;
    }
    TreeNode current = head;
    final Stack<TreeNode> stack = new Stack<>();
    
    while (!stack.isEmpty() || current != null) {
        // 顺着左边界一直走到底
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            // 如果左边界已经走到底了，则从栈中弹一个节点出来，并且将current指针指向弹出节点的right节点，继续上面while循环
            final TreeNode node = stack.pop();
            // 弹出就打印
            System.out.print(node.data + ",");
            current = node.right;
        }
    }
    
}

方式二、用递归实现

/**
 * 递归的方式实现深度优先遍历
 */
public static void deepPriority02(final TreeNode head) {
    if (head == null) {
        return;
    }
    inOrderTraversalProcessor(head);
}

/**
 * 中序遍历二叉树（也是深度优先遍历）
 */
public static void inOrderTraversalProcessor(final TreeNode head) {
    // base case
    if (head == null) {
        return;
    }
  	// 处理左子树
    inOrderTraversalProcessor(head.left);
    // 中序遍历，左子树递归返回就打印
    System.out.print(head.data + ",");
    // 处理右子树
    inOrderTraversalProcessor(head.right);
}

这篇关于java数据结构与算法之二叉树深度优先和广度优先遍历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！