（浙大-19-夏-数据结构学习笔记）二叉树的遍历（递归 非递归）

递归遍历

1. 先序遍历
   遍历过程为：
   ① 访问根结点；
   ② 先序遍历其左子树；
   ③ 先序遍历其右子树。

void PreOrderTraversal(BinTree BT)//先序遍历 {	 if(BT)	 {		  printf("]",BT->Data);		  PreOrderTraversal(BT->Left);		  PreOrderTraversal(BT->Right);	 }} 

2. 中序遍历
遍历过程为：
① 中序遍历其左子树；
② 访问根结点；
③ 中序遍历其右子树

void PreOrderTraversal(BinTree BT)//中序遍历 {	 if(BT)	 {		  PreOrderTraversal(BT->Left);		  printf("]",BT->Data);		  PreOrderTraversal(BT->Right);	 }}

3. 后序遍历
   遍历过程为：
   ① 后序遍历其左子树； ② 后序遍历其右子树； ③ 访问根结点。
   
   

void PostOrderTraversal( BinTree BT ){    if( BT ) {         PostOrderTraversal( BT->Left );         PostOrderTraversal( BT->Right);         printf(“%d”, BT->Data);    }}

非递归遍历

1. 先序遍历

void InOrderTraversal( BinTree BT ) {      BinTree T = BT;    Stack S = CreatStack( MaxSize ); //创建并初始化堆栈S    while( T || !IsEmpty(S) )    {       while(T) //一直向左并将沿途结点压入堆栈       {             printf(“]”, T->Data); //（访问）打印结点           Push(S,T);           T = T->Left;       }       if(!IsEmpty(S))       {           T = Pop(S); /*结点弹出堆栈*/               T = T->Right; /*转向右子树*/       }    }}

2. 中序遍历

void PreOrderTraversal(BinTree BT)//中序遍历 ，非递归{    BinTree T = BT;    Stack S = CreatStack(Maxsize);    while( T || !IsEmpty(S) )    {   	 while( T )   	  {   		   Push(S,T);   		   T = T->Left;   	  }   	  if(!IsEmpty(S) )   	  {   		   T = Pop( S );   		   printf("]",T->Data);   		   T = T->Right;   	   }    } } 

3. 后序遍历

void PostorderTraversal(BinTree BT)//序遍历 ，非递归{   BinTree T = BT;   Stack S = CreateStack(MaxSize);   while(T || !isEmpty(S))//只要没有完全输出，包括在堆栈中的和二叉树中的元素，一直进行循环   {       while(T)       {           Push(S, T);           T = T->left;       }       T = Pop(S);  //没有左子节点时，先拿出此节点       if(!isEmpty(S))       {           if(T->right)  //判断是否有右子节点，如有，再压入栈，进入下一层；如没有则访问           {               Push(S, T);               T = T->right;           }           else           {               printf("]", T->Data);               T = NULL;  //将当前已访问节点置为NULL，防止回到上一层时重复遍历           }       }   }}

来源：https://www.icode9.com/content-4-352101.html