-
2020-11-23 20:30:09
Today,叨叨Chen继续给大家分享算法啦。层次遍历二叉树是大家再熟悉不过的二叉树操作了,看到这个算法通常会联想到队列,没错,叨叨Chen设计的层次遍历算法也是用到了队列(先进先出),下面一起进入算法游乐场吧。
It's show time!
Punchline-------------------------------------------------------------------
Task:用户以广义表的形式输入二叉树,以此创建二叉树,再通过层次遍历算法将二叉树输出,输出的结点之间用空格表示,行末不需要多余的空格。
Input:输入一行,以广义表的形式表示的二叉树。
Output:输出也是一行,为该二叉树按层次遍历的结果序列,每个元素之间用空格隔开,行末不需要多余的空格。
Realize:
- 创建二叉树(createTree):根据广义表的形式创建二叉树,那么会联想到用栈的方法;
- 层序遍历输出二叉树(Layerprint):一层一层从左至右读取、获取数据,思路如下,
- 初始化队列,如果树不为空,则先将根结点入队,判断队列是否为空,进入循环;
- 在循环里,出队,读取数据;
- 输出空格,但需要判断情况,有三种情况:(1)当前队列不为空;(2)队列为空,但是出队列的结点有左孩子;(3)队列为空,但是出队列的结点有右孩子;【(2),(3)的情况可以举个例子更形象,比如当你将根结点入队后,紧接着又出队列读取数据,此时队列是空的,但是如果其有孩子,那么就应该继续输出空格。】
- 如果根结点有左孩子,则左孩子入队列;如果根结点有右孩子,则右孩子入队列,进入下一次循环。
----------------------------------------------------------------------Time---
//加载库;这里不再多说了,详细情况请看叨叨Chen的往期文章。
#include
note:这里使用宏定义来设置Max的值,是为了限制输入的广义表形式的最大长度。当然读者可以使用“const int Max=40;”,叨叨Chen使用宏定义是为了更加熟悉宏定义的本质含义——替换思想。
//定义树的结点(Node),链式队列的结点(QNode,Queue,可以这么理解,QNode是队列里存储元素值域和指针域的结构体,Queue是存储了两个指向QNode的指针的结构体,具体细节可自行查阅链式队列的资料。)
typedef
note:
- 为了更清楚理解结构体的相互使用,叨叨Chen这里没有使用结构体嵌套的方法,读者可以自己设计一下。这里可以很清楚的看到,QNode的结点里是存放的Node(树结点)类型的。
- 从工程的角度来说,读者可以将头文件和定义的结构体放在头文件(xxx.h)里,在源文件里加载头文件(#include"xxx.h";)即可。
//实现Task的功能如下:
//根据二叉树的广义表形式创建二叉树
//主函数
int
note:这里有读者会觉得cin.getline()没必要,但是请思考一个问题,如果用户只输入一个空格呢,这时候,如果用cin,鼠标会一直闪烁,不会进入程序的下一步,就没办法得到树为空的反馈。
嘿嘿嘿~快乐的时光总是短暂的,又到了。。。。。。
欢迎读者提出批评和建议,叨叨Chen会采取好的建议追加在文章后面,大家一起学习喔!
2020.10.09------------------------------------------------------------------It still comes---
更多相关内容 -
层次遍历创建二叉树
2022-05-31 22:57:33层次遍历无法确定一棵二叉树。 假设遍历数组为:[1、2、3、4、5、6] 那么二叉树既可以是这样的 也可以是这样的 因此如果需要根据层次遍历数组来确定一棵二叉树,那么这个数组一定对应了一棵完全二叉树。 假定使用-1...层次遍历无法确定一棵二叉树。
假设遍历数组为:[1、2、3、4、5、6]
那么二叉树既可以是这样的
也可以是这样的
因此如果需要根据层次遍历数组来确定一棵二叉树,那么这个数组一定对应了一棵完全二叉树。假定使用-1表示空节点,数组如下:[1、2、3、-1、4、5、-1、-1、-1、6]。
构造算法如下:type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func createTreeFromLevelOrder(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{ Val: nums[0], } createTree(root, 0, nums) return root } func createTree(node *TreeNode, index int, nums []int) { if node == nil { return } left := 2 * index + 1 if left < len(nums) && nums[left] != -1 { node.Left = &TreeNode{ Val: nums[left], } createTree(node.Left, left, nums) } right := 2 * index + 2 if right < len(nums) && nums[right] != -1 { node.Right = &TreeNode{ Val: nums[right], } createTree(node.Right, right, nums) } }
参考资料:
https://www.linkedin.com/pulse/create-binary-tree-from-array-suhasis-saha/ -
建立二叉树:已知层次遍历顺序建立二叉树、已知先序遍历顺序建立二叉树
2020-09-03 20:33:16二、已知层次遍历顺序,构建二叉树。(链式存储) 三、已知节点关系,建立二叉树(邻接表存储) 四、已知先序和中序遍历顺序,建立二叉树。 前提知识: 约定: 约定二叉树的内容为int类型,并且都>=1,0...其他二叉树知识!二叉树知识汇总
目录
前提知识:
约定:
约定二叉树的内容为int类型,并且都>=1,0代表是空节点。我们一般画的二叉树为图一,但是计算机中存储时真实的样子是图二,即需要考虑空节点,不然的话,计算机不知道这个节点已经到头了。
例子中树的先序遍历为:1 2 4 3 5 6
若是考虑每个节点的两个空节点,则先序遍历为:1 2 4 0 0 0 3 5 0 0 6 0 0
二叉树节点的存储结构:
struct Node{ int data; Node* leftchild; Node* rightchild; };
一个存储数据的data,左右两个指针都是节点的指针类型。
创建一个节点:
void Create_Node(Node* &t,int x){ //在指针t处生成一个新的节点,内容为x t=new Node; t->data=x; t->leftchild=NULL; t->rightchild=NULL; }
开辟一个新的Node类型空间,并将地址赋值给指针t。(原来t指向NULL,现在指向了我们生成的新节点,这就是创建节点的过程)
另外新节点*t的左右孩子要指向NULL,这代表节点到此结束,不赋初值会导致一些错误。
参数的问题:
Node * &t 这个参数表示传入的是一个Node类型的指针变量,并且是引用传递,因为我们要修改实参的值,所以要用引用传递。
不懂引用的看这里:https://blog.csdn.net/qq_21989927/article/details/107447970
建立二叉树的几种方法:
一、已知先序遍历顺序,构建二叉树。(链式存储)
这里的先序遍历顺序,必须是包含空节点的,不然是无法确定二叉树的。
样图中的数的先序遍历顺序:1 2 4 0 0 0 3 5 0 0 6 0 0
void Create_Pre(Node* &t){ int x; cin>>x; if (x==0) return; else{ Create_Node(t,x); Create_Pre(t->leftchild); Create_Pre(t->rightchild); } }
对于输入的x,若是0,说明是空节点,直接返回return。
若不是空节点,则调用前提知识中的Create_Node函数,在此处创建一个新节点,接着再递归新节点的左右孩子。
因为已知的是先序遍历顺序,所以我们是按先访问根,再访问左右孩子的顺序。
二、已知层次遍历顺序,构建二叉树。(链式存储)
这里又分两种方法:一种是边读入数据边建立二叉树,需要用到队列;另一种是已知的层次遍历顺序在数组中存放好了。
1.使用队列
这种方法样例对应的读入是:1 2 3 4 0 5 6 0 0 0 0 0 0 (0是空节点)
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(); 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(); } }
使用队列的方法,首先要入读一个x,判断这棵树是否存在,若是0,说明空树,不为0,创建节点后入队。
当队列不为空时,队列中每一个元素都需要再读取两个数字(就算是叶子节点也起码也得读两个0)。
这种方法建立二叉树,执行过程中会发现,每次读取的两个数,对应的都是队首元素的左右孩子,这和给定的层次遍历顺序对应。
2.使用数组
给定的层次遍历已经存放在数组中,我们只需要判断一个节点的左右孩子是否存在即可,左孩子为i*2,右孩子为i*2+1。
注意要从a[1]开始存储,a[0]不用。
int a[100]={0,1,2,3,4,0,5,6}; void Create_Tree(Node* &t,int i){ if (a[i]==0) return; Create_Node(t,a[i]); if (a[i*2]!=0) Create_Tree(t->leftchild,i*2); if (a[i*2+1]!=0) Create_Tree(t->rightchild,i*2+1); }
3.两种方法的区别:
建造过程的不同:
利用队列,树是一层一层被构造出来的,对数据的访问也是严格按照层次遍历的顺序执行的;
利用数组,树的构造过程实际上是先根,再左孩子,再右孩子的。通过跳跃访问数组内容,实现的是先序遍历建立二叉树。
输入数据的不同:
如果一棵树如图:
对于队列的方法, 输入为 1 0 3 5 6 0 0 0 0
对于数组的方法,数组中:1 0 3 0 0 5 6 0 0 0 0
因为对于队列来,如果一个节点为空节点,那么自然不会加入队列,也不会再去访问他。
而对于数组来说,要严格执行左孩子是*2,右孩子是*2+1的规则,所以空间浪费会很多。
三、已知节点关系,建立二叉树(邻接表存储)
假设题目输入中,我们只知道 x , y 之间有一条边,但是并不知道 x , y 的父子关系的时候,可以使用邻接表的方法存储树。
这时候把树看做一个图,建边要建双向边,然后在从根做dfs,确定每个节点的深度,顺便也可以求出每个节点的父亲节点,这样节点之间的父子关系就清楚了。例题:
第一行输入N、root,表示这棵树有N个节点,根为root。
接下来 N-1 行每行包含两个正整数 x, y,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以构成树)。求每个节点的深度和每个节点的父亲节点。
代码:
#include<iostream> using namespace std; const int MaxN=500050; struct Edge{ int v; int next; }; Edge e[MaxN]; int last[MaxN]; int n,m,root,tot; int deep[MaxN]; int f[MaxN]; void build(int x,int y){ tot++; e[tot].v=y; e[tot].next=last[x]; last[x]=tot; } //编号为x的节点,父亲是fa void dfs(int x,int fa){ f[x]=fa; deep[x]=deep[fa]+1; for (int j=last[x]; j!=0; j=e[j].next){ int y=e[j].v; if (y!=fa) dfs(y,x); } } int main(){ cin>>n>>root; for (int i=1; i<=n-1; i++){ int x,y; cin>>x>>y; build(x,y); build(y,x); } dfs(root,0); for (int i=1; i<=n; i++) cout<<deep[i]<<" "; cout<<endl; for (int i=1; i<=n; i++) cout<<f[i]<<" "; cout<<endl; }
此种方法不仅适合二叉树,也适合多叉树。
四、已知先序和中序遍历顺序,建立二叉树。
LeetCode的题目:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
建立如下二叉树并返回根节点。
3
/ \
9 20
/ \
15 7思路就是递归分治。 对于一个先序遍历序列,第一个一定是根节点,如样例的3。我们只要在中序遍历序列中找到这个3,那么3之前的都是左子树,之后的都是右子树。再依次递归处理即可。
因为题目说不含重复数字,所以在中序遍历中找根的这个工作可以借助哈希表。
还要注意,因为我们递归的是中序遍历的序列,所以还要再加一个参数用来记录此序列的先序遍历第一个是谁,也就是根节点是谁。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: unordered_map<int,int> h; TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n=inorder.size(); for (int i=0; i<n; i++) h[inorder[i]]=i; //哈希求位置 TreeNode* head=build(preorder,inorder,0,n-1,0);//0~n-1 根是0 return head; } TreeNode* build(vector<int>& preorder,vector<int>& inorder,int l,int r,int g){ if (l>r) return NULL; TreeNode* t=new TreeNode(preorder[g]); //构造函数 int j=h[preorder[g]]; //在inorder找pre[g] t->left=build(preorder,inorder,l,j-1,g+1); t->right=build(preorder,inorder,j+1,r,g+j-l+1); return t; } };
-
c++根据二叉树的层次遍历建立二叉树_LeetCode 第 107 号问题:二叉树的层次遍历 II
2020-11-21 14:15:10本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。...题目描述给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)例如: 给定二叉树 ...本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。
个人网站:https://www.cxyxiaowu.com题目来源于 LeetCode 上第 107 号问题:二叉树的层次遍历 II。题目难度为 Easy,目前通过率为 55.8% 。
题目描述
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如: 给定二叉树
[3,9,20,null,null,15,7]
,3 / 9 20 / 15 7
返回其自底向上的层次遍历为:
[ [15,7], [9,20], [3] ]
题目解析
该问题需要用到队列,解法与上篇每天一算:Binary Tree Level Order Traversal类似,区别在于最后存储方式的不同。
- 建立一个 queue
- 先把根节点放进去,这时候找根节点的左右两个子节点
- 去掉根节点,此时queue里的元素就是下一层的所有节点
- 用 for 循环遍历,将结果存到一个一维向量里
- 遍历完之后再把这个一维向量插入到二维向量里
- 以此类推,可以完成层序遍历
动画描述
代码实现
-
广义表形式建立二叉树,并按层次遍历该二叉树
2012-05-18 23:23:35二叉树采用二叉链表结构表示。设计并实现如下算法:输入某棵二叉树的广义表形式,建立该二叉树,并按层次遍历该二叉树 -
java层次遍历二叉树
2021-03-11 15:12:13思路很简单。通过队列,先将头结点放入队列,再遍历每个节点的左节点和右节点。.../*** 遍历层次二叉树** @author chenjunxu**/public class Main {public static void main(String[] args) {// 队列LinkedLis... -
二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择
2022-05-06 18:36:13主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序... -
层次遍历输出二叉树
2020-08-14 22:22:06利用层次遍历算法,输出二叉树的各个结点.说明:需事先利用括号扫描法创建一个二叉链bt,该二叉树bt的括号表示法对应的字符串为"A(B(D(G),H),C(E(F,I)))" #include "stdio.h" #include "stdlib.h" #include "ctype.h... -
层次遍历构建二叉树
2017-05-22 21:00:49struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };TreeNode* createTree(vector<string> nodes) { int len -
按照层次遍历顺序构造二叉树
2022-04-29 18:04:36构造二叉树时,默认二叉树是一颗满二叉树,数组的顺序则是满二叉树的层次遍历结果,其中’#‘代表空节点,以此来构造一颗二叉树。 package main import "fmt" type BinaryTreeNode struct { val rune LeftNode... -
c++根据二叉树的层次遍历建立二叉树_103. 二叉树的锯齿形层次遍历
2020-11-21 13:03:40103. 二叉树的锯齿形层次遍历给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / 9 ... -
层次顺序遍历二叉树 (二叉树层序遍历)
2021-10-28 22:50:13输出层次遍历节点的编号,每层按从左到右顺序输出。 【样例输入】 AB#D##C## 【样例输出】 ABCD //层次顺序遍历二叉树 #include<stdio.h> #include<stdlib.h> #include<string.h> #define... -
按照层次遍历建立一个二叉树
2020-09-17 11:26:27package com.atguigu.springboot.bean.binary; import sun.reflect.generics.tree.Tree; import java.util.*; class TreeNode { TreeNode left; TreeNode right; int val;...public class CreateTwo. -
C语言按层次遍历二叉树算法
2021-05-21 08:51:30下面是编程之家 jb51.cc 通过网络收集整理的代码片段。编程之家小编现在分享给大家,也给大家做个参考。#define MaxSize 1000typedef char ElemType;typedef struct node{ElemType ...//创建二叉树void CreateBTNo... -
二叉树层次遍历与创建
2020-06-13 14:59:212、层次遍历二叉树。输入二叉树头节点的指针。先将头节点入队,将结点指针交给P,后出队。然后再将P左右孩子入队。循环至全部遍历。 注意递归创建过程: 因为先序创建二叉树是左右递归创建,所以一个结束符是结束了... -
c++根据二叉树的层次遍历建立二叉树_LeetCode 第 103 号问题:二叉树的锯齿形层次遍历
2020-11-21 14:15:17本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。...题目描述给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。例如... -
c++根据二叉树的层次遍历建立二叉树_leetcode No.102 二叉树的层次遍历
2020-11-21 13:03:42前两天说过二叉树的前序遍历、中序遍历、后续遍历,把剩下的也都说了吧,二叉树遍历系列四,层次遍历。题目链接:二叉树的层次遍历 - 力扣(LeetCode)leetcode-cn.com题目描述:给定一个二叉树,返回其按层次遍历... -
C++层次遍历输入二叉树(用STL)
2020-03-11 15:20:14C++层次遍历输入二叉树(用STL) 在设置队列的时候,注意类型是queue<Node *> Tqueue,如果不写星号,push时会创建一个新的节点入队,这样整棵树就不是连通的;而加了星号,是把指针地址入队,所以在操作的... -
c语言实现二叉树的建立以及二叉树的先序遍历和层次遍历
2022-04-04 15:23:17首先建立一个二叉树节点的结构体: 节点的左右孩子用lchild和...建立二叉树的结构体: 树都有一个根root typedef struct binarytree{ node*root; }binarytree; 定义建立一颗二叉树的函数: binarytree* makebt -
c++根据二叉树的层次遍历建立二叉树_详解二叉树遍历(前序、中序、后序、层次遍历、深度、广度优先)
2020-11-23 22:06:06二叉树有多种遍历方法,有层次遍历、深度优先遍历、广度优先遍历等。涉及到的代码都用Java编写。1. 首先给出二叉树节点类树节点:class TreeNode { int val; //左子树 TreeNode left; //右子树 TreeNode right; //... -
层次遍历和中序遍历序列创建二叉树
2019-12-01 18:25:15//由层次遍历和中序遍历序列生成二叉树的办法(自己的办法):二叉树的根节点在层次遍历序列中要先于 //其子树首先被访问,所以层次遍历序列中第一个与中序序列中匹配的字符为中序序列的根结点 BTNode* CreateBTree... -
二叉树的层次遍历
2021-02-03 20:51:19层次遍历即为从上到下,从左到右依次访问二叉树的每个结点。 二、层次遍历实现 1、实现思路 (1)我们定义一个队列,先将根结点入队; (2)当前结点是队头结点,将其出队并访问; (3)若当前结点的左结点不为空将... -
【PTA】二叉树的层次遍历
2021-05-07 12:25:42二叉树的层次遍历 编写程序,要求实现 (1)按先序遍历序列建立二叉树的二叉链表;(2)按层次遍历二叉树。 C++: 构成二叉链表的结点类代码如下: typedef struct BiNode { char data; //结点数据域 struct BiNode... -
python按照层序遍历建立二叉树(详细注释)
2020-03-10 10:34:00通常用创建队列,逐层加入元素检查某层是否满,直到发现空位置的方法解决。本代码增加一种输入’#'字符的情况,表明该节点存储的数据为空。 #构造二叉树并实现访问操作,输入#代表树中相应节点的数据是none #本题的... -
层次遍历二叉树
2015-06-29 23:17:51层次遍历二叉树 void CreateBiTree(BiTree &T) //先序法建立二叉树 { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch;... -
c语言实现层次遍历二叉树完整代码
2022-07-09 09:34:49c语言实现层次遍历二叉树完整代码 -
二叉树:层次遍历
2022-05-11 21:26:56目的:使用C++模板设计并逐步完善二叉树的抽象数据类型(ADT)。 内容:(1)请参照链表的ADT模板,设计二叉树并逐步完善的抽象...(2)基本操作5:在二叉树的二叉链表存储形式建立的基础上,设计二叉树的层次遍历算 -
二叉树层次遍历算法
2020-08-27 01:23:39层次遍历 其实记住以上的输出顺序还是非常简单的。首先要明白,左节点一定先比右节点输出! 那么就很好理解了,那么那些所谓的前序、中序、后序而言是针对根节点的相对位置命名的。 例如前序遍历,则就是根节点是最...