数据结构——二叉树的非递归算法

灰太狼 2022-12-26 13:26 190阅读 0赞

## 二叉树的非递归算法 ##

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

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

#### 非递归交换左右孩子算法 ####

使用栈来实现二叉树的非递归算法  
栈的基本算法

先序遍历非递归算法1

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

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

void preorder1(BiTree T)//先序遍历算法1 
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	if(T!=NULL)
    	{
        
    		Push(st,T);//根结点进栈
    		while(!StackEmpty(st))//栈不为空时循环
    		{
        
    			Pop(st,p);
    			printf("%c ",p->data);//退栈结点p并访问
    			
    			if(p->rchild!=NULL)//有右孩子时将其进栈
    				Push(st,p->rchild);
    				
    			if(p->lchild!=NULL)//有左孩子时将其进栈
    				Push(st,p->lchild);
    		}
    	}
    }

先序遍历非递归算法2  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 3]

void preorder2(BiTree T)//先序遍历算法2 
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	p=T;
    
    		while(!StackEmpty(st)||p!=NULL)
    		{
        
    			while(p!=NULL)//访问结点p及其所有左下结点并进栈
    			{
        
    				printf("%c ",p->data);
    				Push(st,p);
    				p=p->lchild;	
    			}
    			if(!StackEmpty(st))//若栈不空
    			{
        
    				Pop(st,p);//出栈结点p
    				p=p->rchild;//转向处理其右子树
    			}
    		}
       
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 5]

void Inorder2(BiTree T)//中序遍历算法2  
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	p=T;
    
    		while(!StackEmpty(st)||p!=NULL)
    		{
        
    			while(p!=NULL)
    			{
        
    				
    				Push(st,p);
    				p=p->lchild;
    				
    			}
    			if(!StackEmpty(st))
    			{
        
    				Pop(st,p);
    				printf("%c ",p->data);
    				p=p->rchild;
    			}
    		}
       
    }

非递归交换左右孩子算法  
思路：与二叉树的非递归遍历算法相似

void Exchange_lchild_rchild(BiTree T)//交换左右子树算法 
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	if(T==NULL) return; 
    	
    	if(T->lchild!=NULL||T->rchild!=NULL)//只要是非叶子结点 
    	{
        
    		Push(st,T);//根结点进栈
    		while(!StackEmpty(st))//栈不为空时循环
    		{
        
    			Pop(st,p);
    			
    			
    			BiTree temp;
    			temp=p->lchild;
    			p->lchild=p->rchild;
    			p->rchild=temp;
    
    			if(p->rchild!=NULL)//有右孩子时将其进栈
    				Push(st,p->rchild);
    				
    			if(p->lchild!=NULL)//有左孩子时将其进栈
    				Push(st,p->lchild);
    		}
    	}
    		
    	
    }

全部代码（可执行代码）：

#include<stdio.h>
    #include<bits/stdc++.h> 
    typedef int Status;
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef char TElemType;
    
    // ------栈的顺序存储结构表示----------
    #define STACK_INIT_SIZE 100 	// 存储空间初始分配量
    #define STACK_INCREMENT 10 	// 存储空间分配增量
    typedef struct BiNode 
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;
    
    typedef BiNode*  ElemType;
    typedef struct {
        
      ElemType *base; 	// 栈底指针
      ElemType *top; 	// 栈顶指针
      int stacksize; 	// 栈空间大小
    } SqStack;
    
    
    void InitStack(SqStack &S)
    {
        
        // 构造一个空栈S
        if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE 
                                      * sizeof(ElemType))))
            exit(OVERFLOW);     // 存储分配失败
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(SqStack &S)
    {
        
        // 销毁栈S，S不再存在
        free(S.base);
        S.base = NULL;
        S.top = NULL;
        S.stacksize = 0;
    }
    
    void Push(SqStack &S, ElemType e)
    {
        
        if(S.top - S.base >= S.stacksize) {
         // 栈满，追加存储空间
            S.base = (ElemType *)realloc(S.base, (S.stacksize 
                  + STACK_INCREMENT) * sizeof(ElemType));
            if(!S.base)
                exit(OVERFLOW);           // 存储分配失败
            S.top = S.base + S.stacksize;
            S.stacksize += STACK_INCREMENT;
        }
        *(S.top)++ = e;
    }
    
    Status Pop(SqStack &S, ElemType &e)
    {
        
        // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
        // 否则返回ERROR
        if(S.top == S.base)
            return ERROR;
        e = *--S.top;
        return OK;
    }
    
    Status GetTop(SqStack S, ElemType &e)
    {
        
        // 若栈不空，则用e返回S的栈顶元素，并返回OK；
        // 否则返回ERROR
        if(S.top > S.base) {
        
            e = *(S.top - 1);
            return OK;
        }
        else
            return ERROR;
    }
    
    Status StackEmpty(SqStack S)
    {
        
        // 若栈S为空栈，则返回TRUE，否则返回FALSE
        if(S.top == S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    
    
    void CreateBiTree(BiTree &T)//二叉树的创建 
    {
        
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch=='#')
    		T=NULL;
    	else 
    	{
        
    		T=(BiNode*)malloc(sizeof(BiNode));
    		if(!T)
    			exit(-1);
    		T->data=ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    
    void DestroyBiTree(BiTree &T)//二叉树的销毁算法 
    {
        
    	if(T==NULL)
    		exit(-1);
    	else
    	{
        
    		DestroyBiTree(T->lchild);
    		DestroyBiTree(T->rchild);
    		free(T);
    	}
    }
    
    void preorder1(BiTree T)//先序遍历算法1 
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	if(T!=NULL)
    	{
        
    		Push(st,T);//根结点进栈
    		while(!StackEmpty(st))//栈不为空时循环
    		{
        
    			Pop(st,p);
    			printf("%c ",p->data);//退栈结点p并访问
    			
    			if(p->rchild!=NULL)//有右孩子时将其进栈
    				Push(st,p->rchild);
    				
    			if(p->lchild!=NULL)//有左孩子时将其进栈
    				Push(st,p->lchild);
    		}
    	}
    }
    
    void preorder2(BiTree T)//先序遍历算法2 
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	p=T;
    
    		while(!StackEmpty(st)||p!=NULL)
    		{
        
    			while(p!=NULL)//访问结点p及其所有左下结点并进栈
    			{
        
    				printf("%c ",p->data);
    				Push(st,p);
    				p=p->lchild;	
    			}
    			if(!StackEmpty(st))//若栈不空
    			{
        
    				Pop(st,p);//出栈结点p
    				p=p->rchild;//转向处理其右子树
    			}
    		}
       
    }
    
    
    
    void Inorder2(BiTree T)//中序遍历算法2  
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	p=T;
    
    		while(!StackEmpty(st)||p!=NULL)
    		{
        
    			while(p!=NULL)
    			{
        
    				
    				Push(st,p);
    				p=p->lchild;
    				
    			}
    			if(!StackEmpty(st))
    			{
        
    				Pop(st,p);
    				printf("%c ",p->data);
    				p=p->rchild;
    			}
    		}
       
    }
    
    void postorder(BiTree T)
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	p=T;
    	BiTree r;
    	r=NULL;
    	
    	while(p||!StackEmpty(st))
    	{
        
    		if(p!=NULL)
    			{
        
    				Push(st,p);
    				p=p->lchild;
    			}
    		else //（p==NULL） 
    			{
        
    			GetTop(st, p);
    			if(p->rchild&&p->rchild!=r)
    				{
        
    					p=p->rchild;
    					Push(st,p);
    					p=p->lchild;
    				}
    			else
    				{
        
    					Pop(st,p);
    					printf("%c ",p->data);
    					r=p;
    					p=NULL;
    				}	
    			}
    	}
     } 
     
     
    void Exchange_lchild_rchild(BiTree T)//交换左右子树算法 
    {
        
    	BiTree p;
    	SqStack st;
    	InitStack(st);
    	if(T==NULL) return; 
    	
    	if(T->lchild!=NULL||T->rchild!=NULL)//只要是非叶子结点 
    	{
        
    		Push(st,T);//根结点进栈
    		while(!StackEmpty(st))//栈不为空时循环
    		{
        
    			Pop(st,p);
    			
    			
    			BiTree temp;
    			temp=p->lchild;
    			p->lchild=p->rchild;
    			p->rchild=temp;
    
    			if(p->rchild!=NULL)//有右孩子时将其进栈
    				Push(st,p->rchild);
    				
    			if(p->lchild!=NULL)//有左孩子时将其进栈
    				Push(st,p->lchild);
    		}
    	}
    		
    	
    }
    
    int main()
    {
        
    	BiTree T;
    	printf("创建树输入树的先序序列\n");
    	CreateBiTree(T);
    	printf("\n先序遍历算法1：");
    	preorder1(T);
    	printf("\n二叉树交换左右孩子算法");
    	Exchange_lchild_rchild(T);
    	printf("\n先序遍历算法2：");
    	preorder2(T);
    
    	printf("\n中序遍历算法2：");
    	Inorder2(T);
    	
    	printf("\n后序遍历算法1: ");
    	postorder(T);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221120/1dfd5772d5324e3eb674749a5ed59ade.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221120/72666a233e2e422cbe4c3904855ac515.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]: /images/20221120/9c5969676b4f451f90fb005a287b4e53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201205191640738.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201205192857702.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201205192905537.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201205193121357.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201205193209399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70