数据结构 之 二叉树的遍历------先根遍历(五）

提示：本篇章主要讲解数据结构中树的相关知识。

二叉树的遍历

• 遍历二叉树是指以某种次序访问二叉树中的每个结点，并且每个结点仅被访问一次.(沿着某条搜索路线依次访问每个结点)

这里“访问”的含义很广，访问结点所做的操作依赖于具体的应用问题。假设遍历时访问结点仅是输出结点数据域的值，那么遍历的结果将是得到一个线性序列。
由于二叉树有左、右子树，所以遍历的次序不同，得到的结果就会不同。

• 

• 假设 L、T、R 分别代表左子树、根结点、右子树

  对一棵二叉树的遍历可以有6种不同的次序：TLR、TRL、LTR、RTL、LRT、RLT

  如果限定先左后右，那么只有三种访问顺序：TLR、LTR、LRT。分别称作：先根遍历，中根遍历，后根遍历，又称前序遍历，中序遍历，后序遍历

为什么要提出这么多遍历方法？

完全是不同的应用角度出发的。

例如：要判断两个二叉树是否相等，只要子树的根结点不同，那么就不等，显然这是可以用先根遍历实现；

例如：删除二叉树时，必须先删除其左、右子树，然后才能删除根结点，这时就要用后根遍历实现。
可以在具体应用中对遍历方法好好体会，接下来进入正题。

先根遍历二叉树（TLR）

先根遍历二叉树的递归定义为：
若二叉树非空，则：
(1)访问根结点；(2)按先根次序遍历左子树；(3)按先根次序遍历右子树；
否则，遍历结束。

简易口诀：根左右
如下图所示

※先根遍历的顺序为：ABDEGCF

先跟遍历：abdgcefhi

先根遍历二叉树的递归算法（重点）

将访问根结点的操作简化为输出根结点的值
void  Preorder (  BTNode * bt  )
{    
           /* 先根遍历以bt为根的二叉树 */    
            if (bt)     {
             printf(bt->data); /*访问根结点*/          			 Preorder( bt->lchild ); /*先根遍历左子树*/         
             Preorder( bt->rchild ); /*先根遍历右子树*/    
                       }
    }

先根遍历二叉树的非递归算法(了解，但是得会写，很有可能找工作的时候让写一个非递归的)

逻辑过程如下：
对于先根遍历二叉树而言，在访问根结点之后，可以直接找到这个根的左子树进行遍历；但是当左子树遍历完毕之后，还必须沿着已经走过的路线返回到根结点，再通过根结点才能找到它的右子树。

因此，在从根结点走向它的左孩子结点之前，必须根结点的地址存入栈中暂存起来。

左子树遍历完毕之后，再按照后进先出的原则取回栈顶元素，才能找到根结点的地址，最后遍历根的右子树。

先根遍历二叉树的非递归算法

void  Preorder2 ( BTNode  *bt )
{       
p = bt;   
InitStack(s);
        while ( p || !StackEmpty(S) )    
        {         
        if (p)                            /*二叉树非空*/       {    
         printf(p->data) ;     /*访问根结点*/              		
          Push( s,  p ) ;        /*根指针进栈*/           
         p = p->lchild ;       /*p移向左孩子*/      
         }     
        else                           /*栈非空*/     
        {
                 Pop ( s , p ) ;        /*双亲结点出栈/*              
                 	p = p->rchild ;      /*p移向右孩子*/       
        }
  		}
}