二叉树遍历原理 | 深度优先-广度优先 | 栈-队列

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第5天，点击查看活动详情

二叉树遍历原理

二叉树遍历分为深度优先遍历和广度优先遍历

深度优先遍历：

• 利用递归和栈的数据结构，完成深度优先遍历

广度优先遍历

• 利用队列的先进先出的策略，完成广度优先遍历

• 前序遍历：根节点——左子树——右子树
• 是否输出取决于是否符合前序遍历规则(根—左—右)

流程：4-2-1-3-6-5-7

原理：

• 访问根节点4，所以4入栈，输出4；遍历2，2压栈,输出2；遍历1，1压栈，输出1；1左右结点为空，所以1出栈，回到2，遍历2右结点3，3压栈，输出3；遍历3，3压栈；3的左右结点为空，所以3出栈，返回2；2的左右结点遍历过了，所以2出栈，返回4；4的左节点遍历过了，接着遍历4的右结点；遍历6，6压栈，输出6；遍历5，5压栈，输出5；因为5左右结点为空，所以5出栈，返回6；遍历7，7压栈，输出7；7左右结点为空、且6遍历过了，所以7、6依次出栈；整个访问结点都以完成，所以4出栈

中序遍历：先访问左子树——根节点——右子树，按照这个顺序

• 是否输出取决于是否符合中序遍历规则(左—根—右)

流程：1-2-3-4-5-6-7

原理：

• 访问根结点4，所以4入栈，因为此处是中序遍历需要符合(左—根—右)规则，所以不输出4；接着遍历左节点2，2压栈，此处2为根结点也不符合(左—根—右)所以不输出；遍历1，1压栈，输出1；1没有左右结点，1出栈，回到根节点2，输出2；遍历2的右节点3，3入栈，输出3；3左右结点为空，3出栈，回到2，2左右结点已遍历，2出栈，回到4，输出4；遍历4右结点，6入栈；遍历5，5压栈，输出5，5的左右结点为空，5出栈，回到6，且输出6；遍历7，7入栈，输出7；7没有左右结点，7出栈，回到6；7、6、4都已遍历，依次出栈

• 后序遍历：和前面差不多，先访问树的左子树——右子树——根节点
• 是否输出取决于是否符合后序遍历规则(左—右—根)

流程：1-3-2-5-7-6-4

原理：

• 访问根结点4，所以4压栈；访问左节点，2入栈；访问左结点，1入栈，输出1；1左右结点为空，1出栈，回到2结点，此时2结点不能输出，需要符合后序遍历规则(左—右—根)；遍历3，3入栈，输出3；3的左右结点为空，所以3出栈，回到2，输出2；2的子结点已遍历，2出栈，回到4；遍历4的右结点，遍历6，6入栈；访问6的左节点5，5压栈，输出5；5没有子结点，所以5出栈，回到6；遍历6的右子结点，遍历6，7入栈，输出7；7没有子结点，7出栈，回到6，输出6；结点6的左右结点已遍历，6出栈，回到4，输出4，4出栈

• 逐层遍历：把一棵树从上到下，从左到右依次写出来
• 是否输出取决于是否符合后序遍历队列规则(先进先出)(根—左—右)

流程：4-2-6-1-3-5-7

原理：

• 根节点入队列，4进入队列，4出队列，输出4；遍历4的左结点2入队列，4的右结点6入队列；2出队列，输出2；2出队列后，需要对2的左右结点1和3分别入队列；6出队列，输出6；6出队列后，需要对6的左右结点5和7分别入队列；此时树中无左右结点，而队列中，从下至上依次为：1/3/5/6；依次从下至上出队列，输出1/3/5/6

队列和栈区别

• 队列：先进先出（First In First Out）FIFO

  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列

• 栈：先进后出（First In Last Out ）FILO

  栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

深度优先遍历(DFS)

前序遍历(根-左-右)

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树

中序遍历(左-根-右)

中序遍历是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树

后序遍历(左-右-根)

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点

广度优先遍历(BFS)

逐层遍历(上-下 | 左-右)

层次遍历 ，就是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问

深度优先遍历 / 广度优先遍历区别

• 深度优先遍历

  深度优先搜索别名又叫DFS,属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次

• 广度优先遍历

  广度优先搜索别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止

🌼 结语：创作不易，如果觉得博主的文章赏心悦目，还请——点赞👍收藏⭐️评论📝冲冲冲🤞