百度&必应权4, 日IP8000. 查看详情
自助收录

二叉树遍历的几种概念

算法刷题2年前 (2023)更新 江南白衣
404 0 0
二叉树遍历的几种概念

二叉树遍历
从根节点往下查找,先找左子树、直至左子树为空(左子节点逐个入栈、直至左子节点为空),再找右子树(出栈找右子节点)
四种顺序:按照排序时根节点所在的位置分为以下几种。
前序遍历:根左右,第一次经过节点即打印,直到打印null,往回溯,打印右子树,打印顺序:A->B->D->E->C->F->G

二叉树遍历的几种概念中序遍历:左根右,第二次经过该节点时进行打印,即左边回溯时,打印顺序:D->B->E->A->F->C->G

二叉树遍历的几种概念后序遍历:左右根,第三次经过该节点时进行打印,即右边回溯时,打印顺序:D->E->B->F->G->C->A

二叉树遍历的几种概念层序遍历:按照层级,从上往下,从左到右。使用广度优先搜索算法。
三种方法论:
1、递归遍历:使用递归方法遍历
2、迭代遍历:使用迭代方法实现递归函数,与递归等价
3、morris遍历
再来看一个图形,说出他的遍历顺序:

二叉树遍历的几种概念前序遍历(中左右):5 4 1 2 6 7 8
中序遍历(左中右):1 4 2 5 7 6 8
后序遍历(左右中):1 2 4 7 8 6 5

© 版权声明

相关文章

暂无评论

暂无评论...