二叉树的三种非递归遍历

￡神魔★判官ぃ 2022-01-11 02:11 162阅读 0赞

### 【Lehr】【数据结构与算法】【C语言】二叉树的非递归遍历 ###

*  先序遍历
 *   *  代码
     *  思路
 *  中序遍历
 *   *  代码
     *  思路
 *  后序遍历
 *   *  代码
     *  思路

非递归必会用到栈呐！

# 先序遍历 #

## 代码 ##

void PreOrder(BTNode *b)
    {
        
        if(b)
        {
        
        	//准备一个简单的栈
    		BTNode* stack[MaxSize];
    		int top = 0;
    
            BTNode* p = b;
            while(p != NULL || top)
            {
        
                while(p != NULL)
                {
        	
                	//打印本节点
                	printf("%c ", p->data);	
                	//栈这样设计是为了让top==0时表示栈空同时拿来当bool判断为否
                	//存入栈里				
    				stack[++top] = p;
    				//访问左孩子
                    p = p -> lchild;
                }
    			
    			//如果左节点不存在			
                if(top)
                {
         	
                	//找到这个左节点的兄弟右节点
    				p = stack[top--];
                    p = p -> rchild;
                }
            }
        }
    }

## 思路 ##

1）访问p节点，并将p节点入栈;  
2）如果左节点存在，则让p指向左节点，循环1步骤  
3）左节点不在了，则出栈一次，让栈顶元素等于目前节点的亲节点，借此让p指针指向这个左节点的兄弟。  
4）如果右节点存在，就继续1，2，3步骤  
5）如果右节点不存在，则再次出栈，栈顶元素等于该节点的亲节点的亲节点。  
6）直到p指向空且栈空才结束。

# 中序遍历 #

## 代码 ##

void InOrder(BTNode *b)
    {
        
        if(b)
        {
        
        	//准备一个简单的栈
    		BTNode* stack[MaxSize];
    		int top = 0;
    
            BTNode* p = b;
            while(p != NULL || top)
            {
        
                while(p != NULL)
                {
        	
                	//先序是在这里打印的!!!!
                	//存入栈里				
    				stack[++top] = p;
    				//访问左孩子
                    p = p -> lchild;
                }
    			
                if(top)
                {
        
                	printf("%c ", p->data);	            	
    				p = stack[top--];
                    p = p -> rchild;
                }
            }
        }
    }

## 思路 ##

1）将p节点入栈;  
2）如果左节点存在，则让p指向左节点，循环1步骤  
3）左节点不在了，则打印该节点并出栈一次，让栈顶元素等于目前节点的亲节点，借此让p指针指向这个左节点的兄弟。  
4）如果右节点存在，就继续1，2，3步骤  
5）如果右节点不存在，则再次出栈，栈顶元素等于该节点的亲节点的亲节点。  
6）直到p指向空且栈空才结束。

与先序唯一的不同就是打印的位置

# 后序遍历 #

## 代码 ##

void PostOrder(BTNode *b)
    {
        
    
    	BTNode* stack[MaxSize];
    	int top = 0;
    
        BTNode *p;    
        BTNode *pre = NULL;    
    
     	stack[++top] = b;
    
        while (top)
        {
        
            p = stack[top];
    
            if((p->lchild==NULL&&p->rchild==NULL)||(pre!=NULL&&(pre==p->lchild||pre==p->rchild)))
            {
        
                printf("%c ", p->data);
    			top--;
                pre = p;
            }
            else
            {
        
                if (p->rchild!=NULL)
                {
        
                	stack[++top] = p->rchild;
                }
                if (p->lchild!=NULL)
                {
        
                	stack[++top] = p->lchild;
                }
            }
    
        }
    }

## 思路 ##