[数据结构与算法]二叉树遍历的本质

我们以递归调用为例

?

code

void OrderTraverse(BinartTree bt)
{


//	这里是先序遍历
  //printf("%d\n",bt->data); 
	
	if(bt->LT)
	OrderTraverse(bt->LT);

//  这里是中序遍历
  //printf("%d\n",bt->data);

	if(bt->RT)
	OrderTraverse(bt->RT);

//	这里是后序遍历
  //printf("%d\n",bt->data);

	
}

我们看到，这里面遍历顺序取决于 printf 函数的位置，

但是，printf 这个函数只是?遍历过程中的操作 ，我们忽略 printf 这个函数。

当我们规定好左子树先于右子树的时候，实际遍历的顺序就已经确定了，显然，没有节点就没有子树，所以遍历的顺序是 根节点 左子树 右子树

用图来体现这个遍历过程

?如图所示，在遍历过程中，对于每个节点来说有三个时期，就是

1. 第一次遇见该节点
2. 遍历完该节点的左子树后
3. 遍历完该节点的右子树后?

显然当我们的遍历操作（例如文章首的例子中的 printf ）在1时期时，就是先序遍历，在2、3时期时则分别是中序遍历、后序遍历。

由此，我们对于二叉树的遍历算法实现的认识就更加清晰。