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

二叉树遍历原理 | 深度优先-广度优先 | 栈-队列二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树

开启掘金成长之旅!这是我参与「掘金日新计划 · 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,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止


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

今天的文章二叉树遍历原理 | 深度优先-广度优先 | 栈-队列分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/18817.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注