用层序遍历建一棵二叉树
2023-09-27 14:23:44 时间
要求用层序遍历的序列建一棵二叉树,并且用先序序列输出
层次遍历序列构造二叉树
让我们先来思考一下怎么层次遍历一棵二叉树:
1.树不为空,root先入队
2.进入循环,循环条件为队列不为空,取出队头元素,队头出队。
3.打印刚刚队头元素的数据。
4.它如果存在左孩子,左孩子入队。
5.它如果存在右孩子,右孩子入队。
6.结束一次循环,回到步骤2
构造二叉树过程和遍历很相似,假设要构造的二叉树的层次遍历序列存在一个数组里
1.只要数组不为空,就先入队数组首元素,并用这个值创建二叉树的root。
2.然后进入循环,循环条件为队列不为空,取出队头元素,队头出队。
3.只要数组还有元素,就先给刚刚拿出的对头元素创建左孩子,然后左孩子入队。
4.同上,再创建右孩子,右孩子入队。
5.结束一次循环。回到2
例:
输入样例:
1 5 12 0 3 0 0 6 0 0 0 0
输出样例:
1 5 12 6 11 3
考虑到有的同学不会用c++中stl里的队列,我们这里分享一种用数组模拟的队列
数组模拟的队列也很好用,效率还高,要注意的是用数组模拟时,空间定义多大?
队列一般有两种情况:
1.如果我们已知有多少元素会入队,开辟一个足够大的计可以。
2.如果我们不知道有多少元素,用一个循环队列就可以。
数组模拟队列(固定大小):
//声明队列
Node* q[MaxSize];
//定义 hh为队头 tt为尾
int hh = 0, tt = -1;
//在队尾加入元素,t是一个节点指针
q[++tt] = t;
//取出队头
Node* s = q[hh++];
//队头出队
hh++;
代码(数组模拟):
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 1010
typedef long long LL;
//树节点的定义
struct Node {
int e;
Node* leftchild, * rightchild;
};
//创建树节点
//传入这个节点指针的地址,为的是传址调用,把这个节点返回回去
void Create_Node(Node*& t,int x) {
t = (Node*)malloc(sizeof(struct Node));
t->e = x;
t->leftchild = t->rightchild = NULL;
}
//层次遍历序列建树
void Create_Level(Node*& t) {
Node* q[MaxSize];//一个队列,元素类型是节点指针
int hh = 0, tt = -1;//头是hh,尾是tt
int x;
cin >> x;
if (x != 0) {
Create_Node(t, x);
q[++tt] = t;
}
while (hh<=tt) {//队列不空就一直循环
Node* s = q[hh++];//取出队头
//创建左右子节点,注意,如果是0代表没有节点,不用管它
cin >> x;
if (x != 0) {
Create_Node(s->leftchild, x);
q[++tt] = s->leftchild;
}
cin >> x;
if (x != 0) {
Create_Node(s->rightchild, x);
q[++tt] = s->rightchild;
}
}
}
//递归先序遍历
void fun(Node* t) {
if (t == NULL)return;
cout << t->e << " ";
fun(t->leftchild);
fun(t->rightchild);
}
int main()
{
//建树
Node* t;
Create_Level(t);
//遍历树(先序)
fun(t);
return 0;
}
代码(c++STL queue):
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
//树节点的定义
struct Node {
int e;
Node* leftchild, * rightchild;
};
//创建树节点
//传入这个节点指针的地址,为的是传址调用,把这个节点返回回去
void Create_Node(Node*& t,int x) {
t = (Node*)malloc(sizeof(struct Node));
t->e = x;
t->leftchild = t->rightchild = NULL;
}
//层次遍历序列建树
void Create_Level(Node*& t) {
queue<Node*> q;//一个队列,元素类型是节点指针
int x;
cin >> x;
if (x != 0) {
Create_Node(t, x);
q.push(t);
}
while (!q.empty()) {//队列不空就一直循环
Node* s = q.front();//取出队头
//创建左右子节点,注意,如果是0代表没有节点,不用管它
cin >> x;
if (x != 0) {
Create_Node(s->leftchild, x);
q.push(s->leftchild);
}
cin >> x;
if (x != 0) {
Create_Node(s->rightchild, x);
q.push(s->rightchild);
}
q.pop();
}
}
//递归先序遍历
void fun(Node* t) {
if (t == NULL)return;
cout << t->e << " ";
fun(t->leftchild);
fun(t->rightchild);
}
int main()
{
//建树
Node* t;
Create_Level(t);
//遍历树(先序)
fun(t);
return 0;
}
运行结果:
相关文章
- leetCode 94.Binary Tree Inorder Traversal(二叉树中序遍历) 解题思路和方法
- 【华为OD机试真题 python】完全二叉树非叶子部分后序遍历-2【2022 Q4 | 200分】
- 【华为OD机试真题 python】 二叉树中序遍历【2022 Q4 | 200分】
- 【算法】【二叉树模块】通过先序遍历和中序遍历获取后序遍历数组(不重构二叉树)
- 【算法】【二叉树模块】树的基本先序、中序、后序遍历算法(7种)
- Google Earth Engine(GEE)——ImageCollection (Error)遍历影像集合产生的错误
- Java二叉树链表的建立及四种遍历方法
- LeetCode高频题:二叉树的锯齿形(Z字形,之字形)层序遍历
- 二叉树的Morris遍历:先序遍历和中序遍历
- 横着打印二叉树的形状,形状真的和二叉树一样,而不是遍历二叉树
- jquery遍历的json有两层list时的解决方法
- 五三想休息,今天还学习,图解二叉树的层序遍历BFS(广度优先)模板,附面试题题解
- 细说数组常用遍历的方法
- 由前序遍历和中序遍历构建二叉树-Python
- 数据结构 有序树转二叉树 (树的遍历)
- 【C++】二叉树之力扣经典题目1——详解二叉树的递归遍历,二叉树的层次遍历
- Java遍历Map对象的四种方式
- 遍历指定文件夹内文件并拼接到一起到指定文件中
- map的遍历
- LeetCode 144. 二叉树的前序遍历
- 从底向上层次遍历二叉树
- LeetCode098之验证二叉搜索树(相关话题:二叉树中序遍历的应用)
- 88、【树与二叉树】leetcode ——226. 翻转二叉树:先中后序的递归与DFS非递归遍历+BFS层次遍历(C++版本)
- 43、【树和二叉树】二叉树的先、中、后和层次遍历方法合集(C/C++版)
- 【刷题笔记】之牛客面试必刷TOP101(二叉树的前.中.后.层序遍历+按之字形顺序打印二叉树+二叉树的最大深度+二叉树中和为某一值的路径(一)+二叉搜索树与双向链表+判断是不是二叉搜索树)
- Java list三种遍历方法性能比较
- 13二叉树的遍历
- iOS - 遍历指定路径下的所有文件(不包括更下级文件)