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

编程汇总 • 2025-03-18 20:33 • 阅读 7

按层序遍历原则，应打印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

#include

#include

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");

}

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

相关推荐