开启掘金成长之旅!这是我参与「掘金日新计划 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,归于一种盲目搜寻法,意图是系统地展开并查看图中的所有节点,以找寻结果。换句话说,它并不考虑结果的或许位置,彻底地查找整张图,直到找到结果停止
结语:创作不易,假如觉得博主的文章赏心悦目,还请——
点赞
收藏
⭐️评论
冲冲冲