首页 > 其他分享 >头歌 第4关:层次遍历二叉树

头歌 第4关:层次遍历二叉树

时间:2024-08-21 16:22:22浏览次数:12  
标签:遍历 队列 SQ QElemType 头歌 二叉树 SqQueue

任务描述
本关任务:给定一棵二叉树,借助队列实现层次遍历二叉树。

相关知识
为了完成本关任务,你需要掌握:1.队列的类型定义及基本操作,2.二叉树层次遍历。

队列的类型定义及基本操作

队列的类型定义:

#define  MAXSIZE 100     //最大长度
typedef BiTNode* QElemType; //队列中数据元素类型
typedef  struct {
  QElemType  *elem;     //数组空间的起始地址
  int front; // 存放队头元素的下标
  int rear;  // 存放队尾元素的下一个位置的下标
 }SqQueue;
队列的基本操作:

队列的初始化:构造一个空队列。具体操作函数定义如下: void SQ_Initiate(SqQueue &Q)
判断队列是否为空:若为空队列,则返回true,否则返回false。该操作函数具体定义如下: bool SQ_IsEmpty(SqQueue Q)
判断队列是否已满:若队列达到最大长度,则返回 true,否则返回false。该操作函数具体定义如下: bool SQ_IsFull(SqQueue Q)
入队:将元素e入队。即:插入元素e为Q的新的队尾元素。该操作函数具体定义如下: void SQ_In(SqQueue &Q, QElemType e)
出队:从队列Q出队一个元素,即:删除Q的队头元素,用e返回其值。该操作函数具体定义如下: void SQ_Out(SqQueue &Q, QElemType &e)
二叉树层次遍历

层次遍历要求先访问离根结点最近的层的结点,然后依次访问下一层的结点。例如:图1的层次遍历的结果为:ABECDF。

编程要求
在右侧编辑器中补充代码,完成HierarchyOrder函数,以实现二叉树的层次遍历。具体要求如下:

* HierarchyOrder:实现二叉树的层次遍历并输出结果,中间没有空格,末尾不换行。

注意:在实现这个函数的函数体内可调用其他操作。

测试说明
可在右侧文件夹中查看step4/Main.cpp文件,以便于你的操作。

平台会对你编写的代码进行测试。

输入说明:
按先序次序输入各结点的值,‘#’表示空树。如创建图1所示二叉树,则输入:ABC##D##EF###

测试输入:
ABC##D##EF###

预期输出:
ABECDF //末尾不换行

开始你的任务吧,祝你成功!

/*************************************************************
    层次遍历二叉树  实现文件 
    更新于2020年6月8日
**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "binary_tree.h"

void SQ_Initiate(SqQueue &Q)
// 顺序队列的初始化,即构造一个空的顺序队列
{
	Q.elem = (QElemType*)malloc(sizeof(QElemType)*MAXSIZE);
	Q.front=Q.rear=0;
}

bool SQ_IsEmpty(SqQueue Q)
// 判断顺序队列是否为空,为空返回true,否则返回false。
{
	return Q.front==Q.rear;	
}

bool SQ_IsFull(SqQueue Q)
// 判断顺序队列是否为满,为满返回true,否则返回false。
{
	return (Q.rear+1)%MAXSIZE==Q.front;	
}

void SQ_In(SqQueue &Q, QElemType e)
// 将e入队。即:插入元素e为Q的新的队尾元素。
{
   	if(SQ_IsFull(Q)) return;//队满
	Q.elem[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;
}

void SQ_Out(SqQueue &Q, QElemType &e)
// 从队列Q出队一个元素,即:删除Q的队头元素,用e返回其值。
{
    if(SQ_IsEmpty(Q)) return; //队空
	e=Q.elem[Q.front];Q.front=(Q.front+1)%MAXSIZE;
}

BiTree CreateBiTree()
// 利用先序遍历创建二叉树,返回根指针。
{
   	BiTree T;char ch;
	ch=getchar();
	if(ch=='#') T=NULL; //'#'代表空树		
	else
	{
		T=(BiTNode *)malloc(sizeof(BiTNode)); //生成根结点
		T->data=ch;
		T->lchild=CreateBiTree( ); //建立左子树
		T->rchild=CreateBiTree( ); //建立右子树
	}
	return T;  
}

void HierarchyOrder(BiTree T)
// 二叉树的层次遍历(借助队列实现)
// 参数:二叉树根指针T
// 输出:二叉树的层次遍历,中间没有空格,末尾不换行。
{
    // 请在这里补充代码,完成本关任务
    /********** Begin *********/
     SqQueue Q;  
    SQ_Initiate(Q); // 初始化队列  
    if (T != NULL) {  
        SQ_In(Q, T); // 将根节点入队  
    }  
    while (!SQ_IsEmpty(Q)) {  
        BiTree current;  
        SQ_Out(Q, current); // 出队,并访问该节点  
        printf("%c", current->data); // 输出节点数据  
        if (current->lchild != NULL) {  
            SQ_In(Q, current->lchild); // 如果左子树不为空,则左子树入队  
        }  
        if (current->rchild != NULL) {  
            SQ_In(Q, current->rchild); // 如果右子树不为空,则右子树入队  
        }  
    }  
    /********** End **********/
}

标签:遍历,队列,SQ,QElemType,头歌,二叉树,SqQueue
From: https://blog.csdn.net/GZH_mxjx/article/details/141282520

相关文章

  • 平衡二叉树、B树、B+树、红黑树解析
    目录有序二叉树平衡二叉树构造平衡二叉树RRLLRLLR平衡二叉树的优缺点:2-3-4树红黑树B树B+树B树、B+树、红黑树的应用有序二叉树关于有序二叉树的详解以及Ja......
  • 【Oracle】存储过程中将动态SQL的多行结果进行循环遍历
    【Oracle】存储过程中将动态SQL的多行结果进行循环遍历需求背景:有一段拼接出来的动态SQL,结果为多行,需要在函数或者存储过程中将其结果作为游标中的数据循环遍历出来以便后续数据操作使用动态SQL和隐式游标隐式游标不支持动态SQL的直接使用,但是可以通过EXECUTEIMMEDIATE来执行......
  • 题解:P10722 [GESP202406 六级] 二叉树
    思路朴素做法当输入\(a_i\)后,直接将它及它的子树进行变换。而这样时间会超时。预计得分\(40\)pts。正解统计每次变换的节点编号,第\(i\)个节点作为根节点进行子树变换的次数为\(rec_i\)。最后从这棵树的根节点\(1\)开始向下dfs,则每个节点变换的次数为\[rec_i+k_j\]......
  • 代码随想录day34 || 62 不同路径,63 不同路径||,343整数拆分,96 不同搜索二叉树
    不同路径funcuniquePaths(mint,nint)int{ //dp五部曲 //dp数组以及下标的含义dp[i][j]代表从0,0走到i,j的不同路径条数 //递推公式 dp[i][j]=dp[i-1][j]+dp[i][j-1] //dp数组的初始化dp[i][0]==dp[0][j]=1 //遍历顺序 外层按照行,内层按照列遍历......
  • 二叉树&堆
    文章目录二叉树&堆1、概念、结构与性质1.1二叉树定义1.2二叉树的特点1.3特殊的二叉树1.4二叉树结构的性质1.5二叉树存储结构1.5.1顺序结构1.5.2链式结构2、实现顺序结构二叉树2.1堆的概念和结构2.2堆的性质2.3二叉树性质2.4堆的实现向上调整法(堆的插入向下调整法(堆的删......
  • 代码随想录算法训练营第11天|二叉树part01
    理论基础需要了解二叉树的种类,存储方式,遍历方式以及二叉树的定义二叉树纯理论方面还是比较简单,以前都学过,没什么可讲的。满二叉树就是满了,完全二叉树就是层满了(而且是左边)。平衡二叉搜索树就是左右深度绝对值差1。一般采用链式存储方式,顺序存储结构如果父节点的数组......
  • python-深层遍历文件夹通过Excel某一列匹配文件夹中的图片(png\jpg)+写入Excel+超链
    目录专栏导读库的介绍背景库的安装完整代码总结专栏导读......
  • [LeetCode] 1367. Linked List in Binary Tree 二叉树中的链表
    Givenabinarytree root anda linkedlistwith head asthefirstnode.ReturnTrueifalltheelementsinthelinkedliststartingfromthe head correspondtosome downwardpath connectedinthebinarytree otherwisereturnFalse.Inthiscontext......
  • 二叉树——14.二叉搜索树的最小绝对差
    力扣题目链接给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。解题思路总结中序遍历是一种有效的方法,可以将二叉搜索树节点的值按从小到大的顺序排列。通过将这些值存入一个有序数组后,只需遍历数组,比较相邻元素的差值,即可找到树中任意两......
  • 二叉树进阶之二叉搜索树:一切的根源
    前言:在学完了简单的容器与C++面向对象的三大特性之后,我们首先接触的就是map与set两大容器,但是这两个容器底层实现的原理是什么呢?我们不而知,今天,主要来为学习map与set的底层原理而打好基础,而二叉搜索树,则是一切的开端......一、二叉搜索树的定义与性质1.1、什么是二叉搜索树:......