c语言实现二叉树层序遍历

末蓝、 2022-05-17 12:49 197阅读 0赞

![70][] 按层序遍历原则，应打印ABCDEFG，如何实现？

1.使用队列，队列是先进先出，首先把A放进去，然后如果队列有元素，就出队A，然后把出队元素A的左右BC节点入队，然后B出队，把B的左右节点放进去（没有就继续出队C），C出队，把DE放进去，D出队，E出队，把FG放进去,然后出FG（因为FG左右节点没有数据,不用入队）,循环条件是队列不能为空（才能实现出队操作）

**核心源码:**

void LevelOrderBinaryTree(pTreeNode t){
    	pQueue pq=(pQueue)malloc(sizeof(Queue));
    	pq=init(pq);
    	enqueue(pq,t);
    	while(pq->rear!=pq->front){
    		pTreeNode x=dequeue(pq);
    		printf("%d ",x->data);
    		if(x->left){
    			enqueue(pq,x->left);
    		}
    		if(x->right){
    			enqueue(pq,x->right);
    		}
    	}
    }

注意：(1).队列不为空即front不等于rear

(2).逻辑要缜密，要出队，实现队列不能为空是把，要入队，首先入队元素不能为空是把

(3).入队后出队，出队要把元素输出（data），然后要把该元素的left，right节点入队，所以要把pTreeNode节点存进去，出队返回该树节点，然后输出该节点的数据，最后把他的左右节点入队

(4).声明结构体，最好多加个结构体指针，在函数传入，只需4个字节，提高效率，不用把整个结构体传进去

**完整代码如下：**

#include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    typedef struct TreeNode{
    	TreeNode *left;
    	TreeNode *right;
    	int data;
    }TreeNode,*pTreeNode;
    
    typedef struct QueueNode{
    	pTreeNode data;
    	QueueNode *next;
    }QueueNode,*pQueueNode;
    
    typedef struct Queue{
    	pQueueNode front;
    	pQueueNode rear;
    }Queue,*pQueue;
    
    void create(pTreeNode *t){
    	int ch;
    	scanf_s("%d",&ch);
    	if(ch==-1){
    		(*t)=NULL;
    		return;
    	}else{
    		(*t)=(pTreeNode)malloc(sizeof(TreeNode));
    		(*t)->data=ch;
    		printf("请输入%d的左节点数据:",ch);
    		create(&((*t)->left));
    		printf("请输入%d的右节点数据:",ch);
    		create(&((*t)->right));
    	}
    }
    
    pQueue init(pQueue pq){
    	pq->front=(pQueueNode)malloc(sizeof(QueueNode));
    	pq->front->next=NULL;
    	pq->rear=pq->front;
    	return pq;
    }
    
    void enqueue(pQueue pq,pTreeNode t){
    	pQueueNode pNew=(pQueueNode)malloc(sizeof(QueueNode));
    	pNew->data=t;
    	pNew->next=NULL;
    	pq->rear->next=pNew;
    	pq->rear=pNew;
    }
    
    pTreeNode dequeue(pQueue pq){
    	pQueueNode pTemp=(pQueueNode)malloc(sizeof(QueueNode));
    	pTemp=pq->front->next;
    	if(pTemp->next==NULL){
    		pq->rear=pq->front;
    	}else{
    		pq->front->next=pTemp->next;
    	}
    	pTreeNode x=pTemp->data;
    	free(pTemp);
    	return x;
    }
    
    void LevelOrderBinaryTree(pTreeNode t){
    	pQueue pq=(pQueue)malloc(sizeof(Queue));
    	pq=init(pq);
    	enqueue(pq,t);
    	while(pq->rear!=pq->front){
    		pTreeNode x=dequeue(pq);
    		printf("%d ",x->data);
    		if(x->left){
    			enqueue(pq,x->left);
    		}
    		if(x->right){
    			enqueue(pq,x->right);
    		}
    	}
    }
    void main(){
    	pTreeNode t;
    	printf("请输入第一个节点数据,-1代表没数据:");
    	create(&t);
    	system("pause");
    	printf("层序遍历如下:");
    	LevelOrderBinaryTree(t);
    	system("pause");
    }

[70]: /images/20220517/639557eb50374cf8a793daa517f113c9.png