二叉树层序遍历C语言版

2022-03-18 22:44:11

二叉树层序遍历C语言版

leetcode 102

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
 
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    * returnSize = 0;
    * returnColumnSizes = malloc(sizeof(int) * 2010);
    if(root == NULL){
        return 0;
    }
    int i = 0;
    struct TreeNode* node;
    int front=0, top = 0;
    struct TreeNode** q = malloc(sizeof(struct TreeNode*) * 2010);
    int** ret = malloc(sizeof(int*) * 2010);
    q[top++] = root; //q[0] = root
    // 队列为空 top==front
    while(top - front > 0){

        int q_size = top - front;
        (* returnColumnSizes)[i] = q_size;
        ret[i] = malloc(sizeof(int) * q_size);
        for(int j =0; j < q_size;j++){
            node = q[front++]; //出队
            ret[i][j] = node->val;   
            if(node->left != NULL)  q[top++]= node->left;     // push
            if(node->right != NULL)  q[top++]= node->right;
        }
        i++;
    }
    * returnSize = i;
    return ret;

}

挺有意思的

更多相关内容

C语言实现二叉树的层序遍历

2021-11-13 12:48:45

贴代码： #include<...//定义二叉树 typedef struct BiNode { char data; struct BiNode* lchild, * rchild; }BiNode,*BiTree; //定义循环队列 typedef struct { BiTree data[MAXSIZE]; int fr

贴代码：

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define MAXSIZE 10

//定义二叉树
typedef struct BiNode {
	char data;
	struct BiNode* lchild, * rchild;
}BiNode,*BiTree;

//定义循环队列
typedef struct {
	BiTree data[MAXSIZE];
	int front;
	int rear;
}Queue;

//初始化队列
int InitQueue(Queue* Q) {
	Q->front = 0;
	Q->rear = 0;
	return OK;
}
//插入队列
int EnQueue(Queue* Q, BiTree bt) {
	if ( (Q->rear+1)%MAXSIZE==Q->front )
	{
		return ERROR;
	}
	Q->data[Q->rear] = bt;
	Q->rear = (Q->rear + 1)%MAXSIZE;
	return OK;
}

//删除队列  注意这里的第二个形参实际上用了二级指针
int DeQueue(Queue* Q, BiTree* bt) {
	if (Q->front==Q->rear)
	{
		return ERROR;
	}
	(*bt) = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return OK;
}

//二叉树的创建
void CreateBiTree(BiTree* T) {
	char c;
	scanf_s("%c", &c);
	if (c==' ')
	{
		(*T) = NULL;
	}
	else
	{
		(*T) = (BiTree)malloc(sizeof(BiNode));
		(*T)->data = c;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

//层序遍历二叉树实现
void LevelOrder(BiTree T) {
	if (T)
	{
		Queue Q;
		InitQueue(&Q);
		EnQueue(&Q, T);
		BiTree bt = NULL;
		while (Q.front!=Q.rear)
		{
			DeQueue(&Q, &bt);
			printf("%c ", bt->data);
			if (bt->lchild)
			{
				EnQueue(&Q, bt->lchild);
			}
			if (bt->rchild)
			{
				EnQueue(&Q, bt->rchild);
			}
		}
	}
}

//主函数测试
int main() {
	BiTree T = NULL;
	CreateBiTree(&T);
	LevelOrder(T);
}

测试结果：
输入： A_ _BD_ _E_ _CF_ _G_ _  ，这里下划线代表空格（测试二叉树在下面）
输出结果： A B C D E F G

待测试的二叉树

收起

展开全文

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

万次阅读 多人点赞 2018-08-11 21:19:11

按层序遍历原则，应打印ABCDEFG，如何实现？ 1.使用队列，队列是先进先出，首先把A放进去，然后如果队列有元素，就出队A，然后把出队元素A的左右BC节点入队，然后B出队，把B的左右节点放进去（没有就继续出队C），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");
}

收起

展开全文

数据结构