首先大家都知道遍历二叉树是很简单的，用递归算法的话代码简洁易懂

void ecsbl( TNode* t )
{
  if( !t ) retuen ;
  操作操作操作操作;
  ecsbl( t->lchild );
  ecsbl( t->rchild );
}

这是前序遍历，把操作放到中间或下面就是中序或者后序遍历，各种遍历的输出顺序不一样。

但如果不用递归，想要遍历整一棵二叉树就要用到额外的数据结构。

深度优先遍历？

想要实现深度优先遍历，就要做到一根条子树到头之前都不换方向，也就是每次都是先输出左(右)子树的数据，再向右(左)移动一位重复输出。想要达成需要用到栈结构。

void depth( TNode* t )
{
 TNode* temp;
 stackin( S, t );   //这里已定义栈stack
 while( ! Isempty(S) )
 {
  stackpop(S, temp);
  if(temp->rchild != NULL)
    stackin(S, temp->rchild);
  if(temp->lchild != NULL)
    stackin(S, temp->lchild);
    //对temp->data操作操作操作
  }
}

每次出栈都伴随着其两棵子树的入栈，循环即可达成深度优先遍历。而在循环中temp永远为刚刚出栈的叶子。

 

广度优先遍历？

深度优先需要先进后出的结构，自然广度优先需要先进先出。这样每次存进去的子树可以马上被释放读取，再读取因释放而被载入的下一层。
很显然，我指的是队列。

void breadth(TNode* t)
{
  TNode* temp;
  queuein(Q, t);
  while( !isEmpty(Q) )
  {
  queuepop(Q, temp);
    if(temp->lchild != NULL)
  queuein(Q, temp->lchild);
    if(temp->rchild != NULL)
  queuein(Q, temp->rchild);
   //对temp->data的操作操作操作
  }
}

有些类似的代码里是利用函数返回写入数据的数组，但鉴于本书作者恶劣的代码风格还有变量名实在令人反胃，这里就直接读取即操作了。