Skip to content
第4章

4.8 二叉树的遍历 ​

三种顺序从哪来 ​

第4章开头问过:层层嵌套的数据,怎么走遍?

线性表一个接一个,从头走到尾就行。二叉树会分叉:A下面有B、C两条路,走了B这边,C那边还得回头再走。所以要先约定一个顺序。

按某个顺序,把每个结点访问一次,而且只访问一次,叫遍历。访问可以是打印、比较、求和,这里就是写下它的名字。

本节问题
4.5节那棵二叉树有A、B、C、D、G五个结点。怎样把每个结点都走到,而且只走一次?写下来是什么序列?

顺序从哪来?回到4.5节的递归定义:

一棵二叉树是三样东西。根,左子树,右子树。走遍整棵树,就是把这三样都走遍。

ABDCG

根有三个位置。三样东西排先后,约定左子树在右子树前面。根只剩三个位置:最前、中间、最后。

根1左2右3
根在最前
左1根2右3
根在中间
左1右2根3
根在最后

子树也照这个顺序。左子树、右子树本身又是二叉树,照同一个顺序走。走到空树,什么也不做,直接回来。

ABDCG

根在最前,叫先序遍历;根在中间,叫中序遍历;根在最后,叫后序遍历。三个名字说的,都是根的位置。

学完这一节,你能写出一棵二叉树的三种遍历序列,用递归函数实现它们,还能说出每种顺序适合做什么。

选中正文里的任意文字,就可以针对它发表评论