先序遍历后序遍历中序遍历-小学生自学网

先序遍历后序遍历中序遍历

作者：来源：发布时间：2013年01月17日点击数：

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的遍历结果是：ABDECF

后序遍历是二叉树遍历的一种。后序遍历指在访问根结点、遍历左子树与遍历右子树三者中，首先遍历左子树，然后遍历右子树，最后遍历访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。后序遍历有递归算法和非递归算法两种。

中序遍历（LDR）

中序遍历也叫做中根遍历，可记做左根右。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：

若二叉树为空则结束返回，

否则：

（1）中序遍历左子树。

（2）访问根结点。

（3）中序遍历右子树。

注意的是：遍历左右子树时仍然采用中序遍历方法。

即左子树（B D E）还是左边开始（D），然后是（B）,再是右边(E)，完后经过(A)，接着右子树（C F）还是左边开始（F）,再是中间（C），

即顺序是DBEAFC

中序遍历的时间复杂度为：O(n)。

如果一棵二叉排序树的节点值是数值，中序遍历的结果为升序排列的数组。可以利用该性质检测一棵树是否为二叉排序数。

上一篇：寄存器