5.二叉树的遍历
6 R8 i" T$ f8 Q. h4 H3 H. [' Q2 s由于二叉树的基本运算在链式存储结构上的实现比较简单,无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。4 g, d+ I& O$ } _: A$ ~+ p% V
遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点,使每个结点恰好被“访问”一次。所谓“访问”一个结点,是指对该结点的数据域进行某种处理,处理的内容依具体问题而定,通常比较简单。遍历运算的关键在于访问结点的“次序”,这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
! B$ A/ E I( h% e( o由定义可知,一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”:$ ?. ~* u. J) r" J
①访问根根点;) D% I0 \" F% Y. z! E1 O$ g0 C
②遍历左子树(即依次访问左子树上的全部结点);③遍历右子树(即依次访问右子树上的全部结点)。
' E# ?: y6 n& A, n, X1 L因为左、右子树都是二叉树(可以是空二叉树),对它们的遍历可以按上述方法继续分解,直到每棵子树均为空二叉树为止。由此可见,上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务,则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”,即子任务②在子任务③之前完成,这样就只剩下前三种次序,按这三种次序进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下:: H0 W9 ]- y W( y# v9 f
先根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
9 N' u" U D. V' ]8 [7 C s①访问根结点;
+ r+ d: h, z0 [6 q( o②先根遍历左子树;
. q# T$ b' x3 c1 K7 e! E8 D: l③先根遍历右子树。3 z6 k* J8 U) c0 ^1 h4 f
中根遍历 若需遍历的二叉树为空,执行空操作,否则,依次执行下列操作:5 F/ H8 x0 k/ A! k
①中根遍历左子树;②访问根结点;③中根遍右子树。 |