|
|
|
遍历是指按某种策略访问树中的每个节点，且仅访问一次。由于二叉树所具有的递归性质，一棵非空的二叉树可以看作由根节点、左子树和右子树三部分构成，因此若能依次遍历这三部分中的每个节点信息，也就遍历了整棵二叉树。按照遍历左子树要在遍历右子树之前进行的约定，根据访问根节点位置的不同，可得到二叉树的前序、中序和后序3种遍历方法。
|
|
|
|
遍历二叉树的基本操作就是访问节点，不论按照哪种次序遍历，对含有n个节点的二叉树，遍历算法的时间复杂度都为O(n)。在最坏情况下，二叉树是有n个节点且深度为n的单枝树，遍历算法的空间复杂度也为O(n)。
|
|
|
|
遍历二叉树的过程实质上是按一定规则，将树中的节点排成一个线性序列的过程，因此遍历操作得到的是树中节点的一个线性序列。在每一种序列中，有且仅有一个起始点和一个终节点，其余节点有且仅有唯一的直接前驱和直接后继。
|
|
|
|
对二叉树还可以进行层序遍历。层序遍历就是从树的根节点出发，首先访问第1层的树根节点，然后从左到右依次访问第2层上的节点，以此类推，自上而下、自左到右逐层访问树中各层上节点的过程。
|
|
|
