二叉树深度优先遍历(DFS)和广度优先遍历(BFS)

定义

二叉树每个节点最多有两个子树结构,分别是“左子树”(left subtree)和“右子树”(right subtree)。

遍历

广度优先遍历(BFS)

广度优先搜索(Breadth First Search),又称层次遍历。从树的根节点(root)开始,然后按照从上到下,从左到右的顺序依次遍历每一层的子节点直到遍历整个树的节点。

深度优先遍历(DFS)

对于一颗二叉树,深度优先遍历(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。树的深度优先遍历主要分为:前序遍历、中序遍历以及后序遍历

  • 前序遍历:若二叉树为空则结束,否则依次先访问根节点,然后访问左子树,最后访问右子树。
  • 中序遍历:若二叉树为空则结束,否则先访问根节点的左子树,然后访问根节点,最后访问右子数。
  • 后序遍历:若二叉树为空则结束,否则先访问根节点的左子树,然后访问右子数,最后访问根节点。

深度优先一般采用递归的方式实现,递归的深度为树的高度。

示例

        0               # 层级遍历:0,1,2,3,4,5,6,7,8,9
/ \ # 前序遍历:0,1,3,7,8,4,9,2,5,6
1 2 # 中序遍历:7,3,8,1,9,4,0,5,2,6
/ \ / \ # 后序遍历:7,8,3,9,4,1,5,6,2,0
3 4 5 6
/ \ /
7 8 9

实现

  • DFS

    使用数据结构栈,(stack

  • BFS

    使用数据结构链表

参考链接