算法:二叉树的遍历

2023-12-17 07:16:29

一、3+1种遍历方法

(1)先序法(又称先根法)
先序遍历:根,左子树,右子树
遍历的结果:A,B,C
遍历的足迹:沿途经过各结点的“左部”

(2)中序法(又称中根法)
中序遍历:左子树,根,右子树
遍历的结果:B,A,C
遍历的足迹:沿途经过各结点的“下部”

(3)后序法(又称后根法)
后序遍历:左子树,右子树,根
遍历的结果:B,C,A
遍历的足迹:沿途经过各结点的“右部”

(4)层次法
层次遍历:从根开始,层次自上到下,同层结点自左至右进行。
遍历的结果:A,B,C
遍历的足迹:第一层A,第二层B,C

二、口诀

先序遍历:?先根?再左?再右

中序遍历:?先左?再根?再右

后序遍历:?先左?再右?再根

三、图片展示

先序遍历结果:A?B?D?H?I?E?J?C?F?K?G

先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果。

中序遍历结果:H?D?I?B?E?J?A?F?K?C?G

中序遍历就是从最左边开始,把每个节点垂直投影到同一直线上,然后从左往右读值就可以了。

后序遍历结果:H?I?D?J?E?B?K?F?G?C?A

就是围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄)(也就是葡萄要一个一个掉下来,不能一口气掉超过1个这样),就把它剪下来,组成的就是后序遍历了。

层次遍历结果:A?B?C?D?E?F?G?H?I?J?K???????

层次遍历很好理解,就是从根节点开始,一层一层,从上到下,每层从左到右,依次写值就可以了。

文章来源:https://blog.csdn.net/Java_1710/article/details/135033058
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。