首页 > 代码库 > 【剑指offer】从上向下打印二叉树

【剑指offer】从上向下打印二叉树

2024-07-05 05:38:59   214人阅读

转载请注明出处：http://blog.csdn.net/ns_code/article/details/26089165


    剑指offer上的第23题，实际上就是考察二叉树的层序遍历，具体思想可以参考这里。

题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行一个整数n(1<=n<=1000, ：n代表将要输入的二叉树元素的个数（节点从1开始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行，每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子，紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子，紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。

输出：

对应每个测试案例，
按照从上之下，从左至右打印出二叉树节点的值。

样例输入：
7
8 6 5 7 10 9 11
d 2 5
d 3 4
z
z
d 6 7
z
z
样例输出：
8 6 10 5 7 9 11
    AC代码：

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

/*
二叉树的存储结构
*/
typedef struct BTNode
{
	int data;
	int rchild;
	int lchild;
}BTNode;

/*
队列的存储结构
*/
typedef struct Node
{
	BTNode data;
	struct Node *pNext;
}NODE,*PNODE;

typedef struct Queue
{
	PNODE front;  //队头指针
	PNODE rear;   //队尾指针
}QUEUE,*PQUEUE;


/*
创建一个空队列，队头指针和队尾指针都指向头结点，
头结点中不存放数据，只存放指针
*/
PQUEUE create_queue()
{
	PQUEUE pS = (PQUEUE)malloc(sizeof(QUEUE));
	pS->front = (PNODE)malloc(sizeof(NODE));
	if(!pS || !pS->front)
	{
		printf("pS or front malloc failed!!");
		exit(-1);
	}
	else
	{
		pS->rear = pS->front;
		pS->front->pNext = NULL;
	}
	return pS;
}

/*
判断队列是否为空
*/
bool is_empty(PQUEUE pS)
{
	if(pS->front == pS->rear)
		return true;
	else
		return false;
}

/*
进队函数，从队尾进队，队头指针保持不变
*/
void en_queue(PQUEUE pS, BTNode e)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(!pNew)
	{
		printf("pNew malloc failed");
		exit(-1);
	}
	else
	{
		pNew->data = http://www.mamicode.com/e;>
/**************************************************************
    Problem: 1523
    User: mmc_maodun
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:916 kb
****************************************************************/


联系
我们