python实现二叉树数据结构的多种遍历方式

  1. 云栖社区>
  2. python技术进阶>
  3. 博客>
  4. 正文

python实现二叉树数据结构的多种遍历方式

python之战 2019-04-12 22:56:56 浏览731
展开阅读全文

二叉树的遍历比较有意思,首先是遍历的方式比较多,大的来说分为深度遍历和广度遍历,深度遍历又分为先序遍历/中序遍历/后序遍历,其中深度遍历用递归来实现,广度遍历用队列来实现。

深度遍历和广度遍历是相对的概念,深度遍历是沿着树的深度遍历树的节点,尽可能深的搜索树的分支;广度遍历是从树的根层级开始一层一层的遍历,遍历完上一层再遍历下一层;如下:

2019-04-12-22_56_01.png

深度遍历顺序:0-1-3-7-8-4-9-2-5-6(先序遍历)

广度遍历顺序:0-1-2-3-4-5-6-7-8-9


但对于深度遍历而言还有三种方式:先序遍历/中序遍历/后序遍历;先序遍历的顺序为:根节点->左子树->右子树;中序遍历为:左子树->根节点->右子树;当然后序遍历是:左子树->右子树->根节点;其中的序指的是根节点相对于左右节点的遍历位置。

在上二叉树中

网友评论

登录后评论
0/500
评论
python之战
+ 关注
所属云栖号: python技术进阶