【数据结构】（二叉树）二叉树的先序中序和后序列遍历递归&&非递归

向右看齐 2021-11-14 12:58 264阅读 0赞

## 递归思想遍历二叉树 ##

**对于递归思想来说只要把握好子问题就可以了。 因为二叉树中每个结点都会被经历三次，其实先序，中序，后序遍历就对应了第一次经历结点时访问，第二次经历访问，第三次经历访问。显而易见递归代码就写出来了如下**

//二叉树先序遍历 
    void preorder(BiTree *b){
        
    	if(b!=NULL){
        
    		visit(b);	
    		preorder(b->lchild);		
    		preorder(b->rchild);	
    	}
    }
    //二叉树后序遍历 
    void postorder(BiTree *b){
        
    	if(b!=NULL){
        
    		postorder(b->lchild);		
    		postorder(b->rchild);
    		visit(b);
    	}
    }
    //二叉树中序遍历
    void Inorder(BiTree *b){
        
    	if(b!=NULL){
        
    	
    		Inorder(b->lchild);
    		visit(b);
    		Inorder(b->rchild);	
    	}
    }

## 非递归代码 ##

**因为递归的本质是借用栈来实现所以非递归也肯定是借用栈来实现的**  
***结构体：***

typedef struct BiTree{
        
    	char data;
    	BiTree *lchild;
    	BiTree *rchild;
    	
    };

void visit(BiTree *b){
        
    	printf("%c  ",b->data);
    }
    
    //**二叉树非递归遍历 先序遍历 
    void pre(BiTree *b){
        
    	
    	BiTree *p;	
    	BiTree *Stack[MaxSize]; 
    	int top=-1;
    	Stack[++top]=b;
    	
    	while(top!=-1){
        
    		p=Stack[top--];
    		visit(p);
    		
    		if(p->rchild!=NULL){
        
    			Stack[++top]=p->rchild;
    		}
    		
    		if(p->lchild!=NULL){
        
    			Stack[++top]=p->lchild;
    		}		
    	} 	
    } 
    //二叉树的中序遍历
    
    void in(BiTree *b){
        	
    	BiTree *Stack[MaxSize]; 
    	int top=-1;
    	while(b!=NULL||top!=-1){
        
    		
    		while(b){
        
    			Stack[++top]=b;
    			b=b->lchild;	
    		}
    		
    		if(top!=-1){
        
    			b=Stack[top--];
    			visit(b);
    			b=b->rchild;				
    		}
    		
    	}	
    } 
    
     
    
    //二叉树的后序遍历 和先序遍历有着相似的思想 首先得到逆后序序列再依次出栈 
    void post (BiTree *b){
        
    	
    	int top=-1; 
    	int top1=-1; 
    	BiTree *p;	
    	BiTree *Stack[MaxSize]; 
    	BiTree *Stack1[MaxSize];
    	Stack[++top]=b;
    	while(top!=-1){
        
    		p=Stack[top--];
    		Stack1[++top1]=p;
    
    		if(p->lchild!=NULL){
        
    			Stack[++top]=p->lchild;
    		}	
    
    		if(p->rchild!=NULL){
        
    			Stack[++top]=p->rchild;
    		}		
    	}
    	while(top1!=-1)
    		visit(Stack1[top1--]);	
    } 
    //二叉树的层次遍历
    
    void leverlOrder(BiTree *p){
        
    	
    	if(p){
        
    		3
    		BiTree *s;
    		BiTree *que[MaxSize+1]; //数组模拟循环队列
    		int front=0,rear=0; 
    		que[rear]=p;
    		rear=(rear+1)%MaxSize; 
    		while(((rear+1-front)%(MaxSize+1)!=0)){
        
    			p=que[front];
    			visit(p); 
    			front=(front+1)%MaxSize;
    			if(p->lchild!=NULL){
        
    				que[rear]=p->lchild;
    				rear=(rear+1)%MaxSize; 
    			}			
    			if(p->rchild!=NULL){
        
    				que[rear]=p->rchild;
    				rear=(rear+1)%MaxSize; 
    			}
    		} 
    		
    	}
    }