二叉树的遍历

系统管理员 2022-02-01 00:43 209阅读 0赞

**遍历顺序**

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]

**规律：**

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>先序遍历</td> 
   <td>当第一次遇见结点就输出</td> 
  </tr> 
  <tr> 
   <td>中序遍历</td> 
   <td>当第一次遇见结点时不输出，第二次遇见结点时就输出</td> 
  </tr> 
  <tr> 
   <td>后序遍历</td> 
   <td>在输出的时候判断一下子树结点是否全都输出，如果全都输出就可以输出此结点</td> 
  </tr> 
 </tbody> 
</table>

--------------------

##### 二叉树的递归遍历 #####

###### 1、定义声明 ######

typedef struct TNode *Position;
    typedef struct TNode *BinTree;
    struct TNode{ 
    	ElemenType Data;
    	BinTree left;
    	BinTree right;
    };

--------------------

###### 2、先序遍历（VLR） ######

void PreorderTraversal(BinTree BT)
    { 
    	if(BT)
    	{ 
    		printf("%d",BT->Data);
    		PreorderTraversal(BT->left);
    		PreorderTraversal(BT->right);
    	}
     }

--------------------

###### 3、中序遍历（LVR） ######

void InorderTraversal(BinTree BT)
     { 
     	if(BT)
     	{ 
     		InorderTraversal(BT->left);
     		printf("%d",BT->Data);
     		InorderTraversal(BT->right);
    	 }
     }

--------------------

###### 4、后序遍历（LRV） ######

void PostorderTraversal(BinTree BT)
    { 
    	if(BT)
    	{ 
    		PostorderTraversal(BT->left);
    		PostotderTraversal(BT->right);
    		printf("%d",BT->Data);
    	}
    }

--------------------

##### 二叉树的非递归遍历 #####

###### > ######

###### 中序遍历 ######

使用堆栈，中序遍历正好符合先进后出规则  
![在这里插入图片描述][20190513112141415.PNG]

void InorderTraversal(BinTree BT)
    { 
    	BinTree T=BT;
    	stack S=CreatStack();
    	while(T||!IsEmpty(S))//如果树未遍历完或堆栈不为空 
    	{ 
    		while(T)//先访问左边，遇到就把它压栈 
    		{ 
    			Push(S,T->Data);
    			T=T->left;
    		 } 
    		 if(!IsEmpty(S))
    		 { 
    		 	T=Pop(S);
    		 	printf("%d",T->Data);
    		 	T=T->right;
    		  } 
    	}
    }

--------------------

###### 先序遍历非递归算法 ######

相对于中序遍历，只是将输出位置改到上面就行

void PreorderTraversal(BinTree BT)
    { 
    	BinTree T=BT;
    	stack S=CreatStack();
    	while(T||!IsEmpty(S))//如果树未遍历完或堆栈不为空 
    	{ 
    		while(T)//先访问左边，遇到就把它压栈 
    		{ 
    			printf("%d",T->Data);
    			Push(S,T->Data);
    			T=T->left;
    		 } 
    		 if(!IsEmpty(S))
    		 { 
    		 	T=Pop(S);
    		 	
    		 	T=T->right;
    		  } 
    	}
    }

--------------------

###### 后序遍历非递归算法O（参考别人的）—only了解 ######

typedef struct BiTNode{ 
    	int data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
     
    typedef struct{ 
    	BiTree data[100];
    	int top;
    }BiStack;
    
    
    void PostOrder(BiTree T){ 	//入栈所有的左子树以及左子树的右子树直到没有可以访问的右子树后退栈。 
    	BiTNode *pre = T;	//记录上一次退栈的结点 
    	BiTNode *p=T;		//当前访问结点 
    	BiStack s ;             //保存结点用的栈
    	s.top=0;                //栈底预留，用于保存NULL结束算法。
    	s.data[s.top]=NULL;
    	while(p||s.top!=0){ 
    		if(p!=NULL&&pre!=p->lchild&&pre!=p->rchild){ 	//结点不为空且左孩子和右孩子没有访问过 ，入栈左子树 
    			s.data[++s.top]=p;
    			p=p->lchild;
    		}
    		else{ 					
    			p=s.data[s.top];						 
    			if(p->rchild!=NULL&&pre!=p->rchild){ 	//右子树不为空且右孩子没有访问过，入栈右子树结点 
    				p=p->rchild;
    			}
    			else{ 
    				printf("%d ",p->data);		//访问到最后的右子树的结点后，退栈。 
    				pre=s.data[s.top];
    				p=s.data[--s.top];
    			}
    		}
    	}
    }

--------------------

##### 层序遍历队列实现 #####

![在这里插入图片描述][20190513214730320.PNG]

void LevelorderTraversal(BinTree BT)
    { 
    	Queue Q;
    	BinTree T;
    	Q=CreatQueue();
    	 
    	if(!BT) return ;//如果是空树
    	 
    	Add(Q,BT);
    	while(!IsEmpty(Q))
    	{ 
    		T=Delete(Q);
    		printf("%d",T->Data);
    		if(T->left) Add(Q,T->left);
    		if(T->right) Add(Q,T->right);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]: /images/20220201/9b136ee6158c4a2fb220285d7b918306.png
[20190513112141415.PNG]: /images/20220201/6ac88ea3e02540a0b4f72ece470d7dc9.png
[20190513214730320.PNG]: /images/20220201/ebe662132d7044dda7ba6bb06c4b21c0.png