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

全栈程序员-站长 • 2022年5月11日上午8:40 • 未分类 • 阅读 38

大家好，又见面了，我是你们的朋友全栈君。

c语言实现二叉树层序遍历按层序遍历原则，应打印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");
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/143210.html原文链接：https://javaforall.net