数据结构——二叉树的遍历问题（C语言）

小鱼儿 2022-08-25 08:38 176阅读 0赞

## **前言** ##

**二叉树的遍历方式有以下几种：递归遍历、非递归遍历（即迭代遍历）和层次遍历。**

## **一、递归遍历：** ##

### **1、先序递归遍历：** ###

**就是从二叉树的根结点开始，先访问结点的数据，再访问二叉树的左子树结点，直到遇到空结点为止。然后，返回到最近的有右儿子的父亲结点，并从该结点的右儿子开始继续遍历。**

**源程序如下：**

void Pre_Order_BinTree(BinTree Ptr)
    {
    	if(Ptr)
    	{
    		printf("%c ",Ptr->data);
    		if(Ptr->L_Child)
    			Pre_Order_BinTree(Ptr->L_Child);
    		if(Ptr->R_Child)
    			Pre_Order_BinTree(Ptr->R_Child);
    	}
    }

### **2、中序递归遍历：** ###

**就是从二叉树的根结点开始，向二叉树的左子树移动，直到遇到空结点为止，然后访问空结点的父亲结点。接着继续遍历该结点的右子树。**

**源程序如下：**

/***中序遍历的递归实现***/
    void Mid_Order_BinTree(BinTree Ptr)
    {
    	if(Ptr)
    	{
    		if(Ptr->L_Child)
    			Mid_Order_BinTree(Ptr->L_Child);		
    		printf("%c ",Ptr->data);
    		if(Ptr->R_Child)
    			Mid_Order_BinTree(Ptr->R_Child);
    	}
    }

### **3、后序递归遍历：** ###

**这种遍历方法是先访问结点的左右子树，再访问该结点。**

**源程序如下：**

/***后序遍历的递归实现***/
    void Post_Order_BinTree(BinTree Ptr)
    {
    	if(Ptr)
    	{
    		if(Ptr->L_Child)		
    			Post_Order_BinTree(Ptr->L_Child);
    		if(Ptr->R_Child)		
    			Post_Order_BinTree(Ptr->R_Child);
    		printf("%c ",Ptr->data);
    	}
    }

## **二、非递归遍历（即迭代遍历）** ##

### **1、先序非递归遍历：** ###

**根据先序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：**

**对于任一结点P：**

**1)访问结点P，并将结点P入栈;再看P的左孩子。**

**2)判断结点P的左孩子是否为空：**

1.  1.  1.  **若不为空，则将P的左孩子置为当前的结点P;重复1)的操作。**
        2.  **若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);**

**3)直到P为NULL并且栈为空，则遍历结束。**

**源程序如下：**

/***前序遍历的非递归实现***/
    void NPre_Order_BinTree(BinTree Ptr)
    {  
        PStack stack = Create_Stack();  //创建一个空栈  
        BinTree pCurrent = Ptr;             //定义用来指向当前访问的节点的指针  
       
        while(pCurrent || !SIs_Empty(stack))  
        {  
    	printf("%c ", pCurrent->data);  
    	Push_Stack(stack,pCurrent);  
            pCurrent = pCurrent->L_Child;   
            while(!pCurrent && !SIs_Empty(stack))  
            {  
                pCurrent = Get_Item_Stack(stack);  
                Pop_Stack(stack);  
                pCurrent = pCurrent->R_Child;              
            }  
        }  
    }

### **2、中序非递归遍历：** ###

**根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：**

**对于任一结点P，**

**1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；**

**2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，**

**然后将当前的P置为栈顶结点的右孩子；**

**3)直到P为NULL并且栈为空则遍历结束。**

**源程序如下：**

/***中序遍历的非递归实现***/
    void NMid_Order_BinTree(BinTree Ptr)
    {  
        PStack stack = Create_Stack();  //创建一个空栈  
        BinTree pCurrent = Ptr;             //定义用来指向当前访问的节点的指针  
      
       while(pCurrent || !SIs_Empty(stack))  
        {  
            Push_Stack(stack,pCurrent);  
            pCurrent = pCurrent->L_Child;  
            while(!pCurrent && !SIs_Empty(stack))  
            {  
                pCurrent = Get_Item_Stack(stack); 
    			printf("%c ", pCurrent->data);  
                Pop_Stack(stack);  
                pCurrent = pCurrent->R_Child;              
            }  
        }  
    }

### **3、后序非递归遍历：** ###

**根据后序遍历的顺序，先访问左子树，再访问右子树，后访问根节点，而对于每个子树来说，又按照同样的访问顺序进行遍历。****要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者 右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元 素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。**

**对于任一结点P，**

**1）先将节点P入栈；**

**2）如果P不存在左孩子和右孩子，或者P存在左孩子或者 右孩子，**

**但是其左孩子和右孩子都已被访问过了，则可以直接访问该结点P，并将其出栈，**

**将出栈结点P标记为上一个输出的节点，再将此时的栈顶结点设为当前节点；**

**3）若不满足2）中的条件，则将P的右孩子和左孩子依次入栈，**

**当前节点重新置为栈顶结点，之后重复操作2）；**

**4）直到栈空，遍历结束。**

**源程序如下：**

/***后序遍历的非递归实现***/
    void NPost_Order_BinTree(BinTree Ptr)
    {
        PStack stack = Create_Stack();  //创建一个空栈  
        BinTree pCurrent;                      //当前结点 
        BinTree pre=NULL;                 //前一次访问的结点 
        Push_Stack(stack,Ptr);
        while(!SIs_Empty(stack))
        {
            pCurrent = Get_Item_Stack(stack); 
            if((pCurrent->L_Child==NULL&&pCurrent->R_Child==NULL)||
               (pre!=NULL&&(pre==pCurrent->L_Child||pre==pCurrent->R_Child)))
            {
                printf("%c ", pCurrent->data);  
                Pop_Stack(stack);
                pre=pCurrent; 
            }
            else
            {
                if(pCurrent->R_Child!=NULL)
    				Push_Stack(stack,pCurrent->R_Child);
                if(pCurrent->L_Child!=NULL)    
                    Push_Stack(stack,pCurrent->L_Child);
            }
        }    
    }

## **三、层次遍历：** ##

**首先把根结点加入队列，判断队列是否为空，不为空，从队列前端删除结点，并输出该结点的数据域，并依次把该结点的左、右孩子加入队列。**

**源程序如下：**

/*******************层序遍历实现********/
    void Level_Order_BinTree(BinTree Ptr)
    {  
        PQueue QP;
    	QP=Creat_Queue();
    	BinTree temp=NULL;
        if(Ptr)  
        {  
            Add_Queue(QP,Ptr);  
            while(!QIs_Empty(QP))  
            {  //注意：若队列为空时，QIs_Empty是返回true；
                temp=Delete_Queue(QP,temp);  
    			printf("%c ",temp->data);  
    			if(temp->L_Child!=NULL) Add_Queue(QP,temp->L_Child);  
    			if(temp->R_Child!=NULL) Add_Queue(QP,temp->R_Child);  
            }  
            printf("\n");  
        }  
    }