数据结构——二叉树的层次遍历

￡神魔★判官ぃ 2022-12-23 09:45 177阅读 0赞

#### 问题描述： ####

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：  
二叉树：\[3,9,20,null,null,15,7\]  
![在这里插入图片描述][20201124165545389.png_pic_center]

返回其层次遍历结果：

\[  
\[3\],  
\[9,20\],  
\[15,7\]  
\]  
通过

来源：力扣（LeetCode）  
[二叉树的层序遍历][Link 1]

#### 目录 ####

1.非递归用循环队列  
2.递归实现层次遍历

在栈与队列：**匹配问题都是栈的强项中**提到，「递归的实现就是：**每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中**」，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

##### 知识前提：循环队列，二叉树的基本运算 #####

## 非递归用循环队列 ##

//思路  
进行层次遍历时构建一个辅助队列，先将二叉树根节点入队，然后出队，访问出队结点，若它有左子树，将左子树根节点入队，然后出队，访问出队结点…，右子树也同样如此，循环往复直到队列为空

1.构建好辅助队列Q和二叉树T；  
2.首先将二叉树的T（根节点）入队列；  
3.进入while循环，退出条件 ：队列为空；  
4.循环内部：首先将队列中的队首元素出栈，并且输出他的值；  
若队首元素（刚刚出队的元素）有左子树，将其左子树入队  
若队首元素（刚刚出队的元素）有右子树，将其右子树入队  
详细代码（可直接运行）

补充：如何让输出为一层一行

方法说起来很简单，只要仔细想，应该都能想出这种方法来。

定义两个变量curLevelCount和nextLevelCount来分别保存当前层和下一层的结点数。

显然，curLevelCount的初始值为1，因为只有一个根结点，而nextLevelCount由于未知，故置为0.

思路：  
1.输出一行一行的与之前输出为一行的代码大体相似  
2.构建好辅助队列Q和二叉树T；  
3.**再定义两个变量：curLevelCount用于记录当前层次结点个数，nextLevelCount用于记录当前层次的下一层结点的个数**  
4.将二叉树的根节点入栈，**同时curLevelCount=1，nextLevelCount=0；**  
5.进入while循环，退出条件 ：队列为空；  
6.循环内部：首先将队列中的队首元素出栈，并且输出他的值；**（与此同时，将curLevelCount–)；**  
若队首元素（刚刚出队的元素）有左子树，将其左子树入队.**(与此同时，将nextLevelCount++);**  
若队首元素（刚刚出队的元素）有右子树，将其右子树入队.**（与此同时，将nextLevelCount++);**  
**若curLevelCount减到零：输出一个换行符，将nextLevelCount赋值给curLevelCount，  
nextLevelCount=0；**  
代码：非递归用循环队列

#include<stdio.h>
    
    typedef int Status;
    #define TRUE  1
    #define FALSE 0
    #define  ERROR 0
    #define  OK 1
    #include<malloc.h> 
    #include<stdlib.h>
    #include<stdio.h>
    #include<bits/stdc++.h> 
    
    typedef char TElemType;
    typedef int status; 
    typedef struct BiNode
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;
    typedef BiTree ElemType;
    typedef BiTree QElemType;
    //----------循环队列 --顺序存储结构-----------------------
    #define  MAXQSIZE  100    // 最大队列长度+1
    typedef  struct {
        
        ElemType   *base;   // 初始化的动态分配存储空间
        int   front;    // 头指针，若队列不空，指向队列头元素
        int   rear;   // 尾指针，若队列不空，指向队列尾元素的下一个位置
    }  SqQueue;
    void InitQueue(SqQueue &Q)
    {
            // 构造一个空队列Q
        Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
        if(!Q.base) // 存储分配失败
            exit(0);
        Q.front = Q.rear = 0;
    }
    void DestroyQueue(SqQueue &Q)
    {
           // 销毁队列Q，Q不再存在
        if(Q.base)
            free(Q.base);
        Q.base = NULL;
        Q.front = Q.rear = 0;
    }
    int QueueLength(SqQueue &Q)
    {
        
    	return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
    }
    Status EnQueue(SqQueue &Q, QElemType e)
    {
           // 插入元素e为Q的新的队尾元素
        if((Q.rear + 1) % MAXQSIZE == Q.front) // 队列满
            return ERROR;
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MAXQSIZE;
        return OK;
    }
    Status DeQueue(SqQueue &Q, QElemType &e)
    {
          // 若队列不空，则删除Q的队头元素，用e返回其值，
       // 并返回OK；否则返回ERROR
        if(Q.front == Q.rear) // 队列空
            return ERROR;
        e = Q.base[Q.front];
        Q.front = (Q.front + 1) % MAXQSIZE;
        return OK;
    }
    Status GetHead(SqQueue Q, QElemType &e)
    {
           // 若队列不空，则用e返回Q的队头元素，并返回OK；
        // 否则返回ERROR
        if(Q.front == Q.rear) // 队列空
            return ERROR;
        e = Q.base[Q.front];
        return OK;
    }
    Status QueueEmpty(SqQueue Q)
    {
        
        // 若队列Q为空队列，则返回TRUE；否则返回FALSE
        if(Q.front == Q.rear) // 队列空的标志
            return TRUE;
        else
            return FALSE;
    }
    void traverse(SqQueue &Q)
    {
        
    	int x;
    	x=Q.front;
    	int num=QueueLength(Q);
    	for(int i=0;i<num;i++)
    	{
        
    		printf("%d--",Q.base[(x++)%MAXQSIZE]);
    	}
    }
    
    
    
    
    
    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);
    	}
    }
    
    
    
    int  preorderTraverse(BiTree T)//二叉树的先序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			printf("%c ",T->data);
    			preorderTraverse(T->lchild);
    			preorderTraverse(T->rchild);
    		}
     } 
     
    int  InorderTraverse(BiTree T)//二叉树的中序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			InorderTraverse(T->lchild);
    			printf("%c ",T->data);
    			InorderTraverse(T->rchild);
    		}
     }
     
    int  PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			PostorderTraverse(T->lchild);
    			PostorderTraverse(T->rchild);
    			printf("%c ",T->data);
    		}
     }
    
    void BiTree_level_traversal1(BiTree T)//按层输出一行 
    {
        
    	SqQueue Q;
    	InitQueue(Q);
    	EnQueue(Q,T);
    	BiTree temp;
     
    	while(!QueueEmpty(Q))
    	{
        
    		DeQueue(Q, temp);
    		printf("%c ",temp->data);
    		if(temp->lchild!=NULL)
    			EnQueue(Q,temp->lchild);
    		if(temp->rchild!=NULL)
    			EnQueue(Q,temp->rchild);
    	}
    	
    	
     } 
     
     
    void BiTree_level_traversal(BiTree T)// 层次遍历输入一层一层的 
    {
        
    	SqQueue Q;
    	InitQueue(Q);
    	EnQueue(Q,T);
    	BiTree temp;
    	int curLevelCount=1,nextLevelCount=0; 
     
    	while(!QueueEmpty(Q))
    	{
        
    		DeQueue(Q, temp);
    		printf("%c ",temp->data);
    		curLevelCount--;
    		if(temp->lchild!=NULL)
    			
    			{
        
    				EnQueue(Q,temp->lchild);
    				nextLevelCount++;
    			}
    			
    		if(temp->rchild!=NULL)
    		{
        
    			EnQueue(Q,temp->rchild);
    			nextLevelCount++;
    		}
    		if(curLevelCount==0)
    		{
        
    			printf("\n"); 
    			curLevelCount = nextLevelCount;
    			nextLevelCount=0;
    		}
    
    			
    	}
    	
    	
     } 
     
     
    int main()
    {
        
    	BiTree T;
    	printf("创建树输入树T的先序序列(其中使用#代表空节点)\n");
    	CreateBiTree(T);
    	
    	
    	printf("先序遍历算法");
    	preorderTraverse(T);
    	printf("\n中序遍历算法");
    	InorderTraverse(T);
    	printf("\n后序遍历算法");
    	PostorderTraverse(T);
    	
    	printf("\n遍历结果为：\n");
    	 BiTree_level_traversal1(T);
    	 printf("\n一层一层的输出\n"); 
    	 BiTree_level_traversal(T);
    }

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

## 递归实现层次遍历 ##

思路：  
1.先利用BiTree\_height1(BiTree T)求二叉树高度算法，求得高度  
2.levelOrder( BiTree T)层次遍历递归算法（这个函数仅一个for循环）**，用for（）将二叉树一层一层的输出，每一层输出完，再输出一个换行符。**  
3.printNodeAtLevel(BiTree T,int level)**（真正的递归遍历输出函数）**。  
若level==0，输入此时的T->data;

int BiTree_height1(BiTree T)//求树的深度算法1 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    	{
        
    		if(BiTree_height1(T->lchild)>BiTree_height1(T->rchild))
    				return 1+BiTree_height1(T->lchild);
    		else
    				return 1+BiTree_height1(T->rchild);
    	
    	}
    	
    	
    } 
    void printNodeAtLevel(BiTree T,int level)  
    {
          
        if(T==NULL||level<0)  
            return;  
      
        if(level==0)  
        {
          
        printf("%c ",T->data);
    	return;  
        }  
      
        // 左子树的 level - 1 级  
        printNodeAtLevel(T->lchild,level-1);  
      
        // 右子树的 level - 1 级  
        printNodeAtLevel(T->rchild,level-1);  
    }
     
    void levelOrder(const BiTree T)
    {
        
    	if(T==NULL)
    		return;
    	int totalLevel = BiTree_height1(T);
    	for(int i = 0; i< totalLevel; i++)
    	{
        
    		printNodeAtLevel(T, i);
    		printf("\n");//打印完一层，换行
    	}
    }

代码：递归实现（全部代码）

#include<stdio.h>
    #include<bits/stdc++.h> 
     
    typedef char TElemType;
    typedef int status; 
    typedef struct BiNode
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;
    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);
    	}
    }
    
    int  preorderTraverse(BiTree T)//二叉树的先序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			printf("%c ",T->data);
    			preorderTraverse(T->lchild);
    			preorderTraverse(T->rchild);
    		}
     } 
     
    int  InorderTraverse(BiTree T)//二叉树的中序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			InorderTraverse(T->lchild);
    			printf("%c ",T->data);
    			InorderTraverse(T->rchild);
    		}
     }
     
    int  PostorderTraverse(BiTree T)//二叉树的后序递归遍历算法 
    {
        
    	if(T==NULL)
    		return 0;
    	else 
    		{
        
    			PostorderTraverse(T->lchild);
    			PostorderTraverse(T->rchild);
    			printf("%c ",T->data);
    		}
     }
     
    int BiTree_height1(BiTree T)//求树的深度算法1 
    {
        
    	if(T==NULL)
    		return 0;
    	else
    	{
        
    		if(BiTree_height1(T->lchild)>BiTree_height1(T->rchild))
    				return 1+BiTree_height1(T->lchild);
    		else
    				return 1+BiTree_height1(T->rchild);
    	
    	}
    	
    	
    } 
    void printNodeAtLevel(BiTree T,int level)  
    {
          
        if(T==NULL||level<0)  
            return;  
      
        if(level==0)  
        {
          
        printf("%c ",T->data);
    	return;  
        }  
      
        // 左子树的 level - 1 级  
        printNodeAtLevel(T->lchild,level-1);  
      
        // 右子树的 level - 1 级  
        printNodeAtLevel(T->rchild,level-1);  
    }
     
    void levelOrder(const BiTree T)
    {
        
    	if(T==NULL)
    		return;
    	int totalLevel = BiTree_height1(T);
    	for(int i = 0; i< totalLevel; i++)
    	{
        
    		printNodeAtLevel(T, i);
    		printf("\n");//打印完一层，换行
    	}
    } 
     
    int main()
    {
        
    	BiTree T;
    	printf("创建树输入树T的先序序列(其中使用#代表空节点)\n");
    	CreateBiTree(T);
    	printf("先序遍历算法");
    	preorderTraverse(T);
    	printf("\n中序遍历算法");
    	InorderTraverse(T);
    	printf("\n后序遍历算法");
    	PostorderTraverse(T);
    	printf("\n二叉树层次遍历算法\n");
    	levelOrder(T);
    	
    	
     }

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

[20201124165545389.png_pic_center]: /images/20221120/8bd4de71805c4d0c8929c6bd6d453bf4.png
[Link 1]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d8c6ac0a9dcb4bda929a8ab080971eb8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/1fa135e719044e2994ca8490f9f34fb1.png