关键词：
运行效果图 结构体指针实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10000
int failed,n,v,ans[N];
char s[N];//保存读入结点
typedef struct Node//结点类型
{
int flag;//是否被赋值过
int number;//结点值
struct Node *left,*right;//左右子结点
}Node;
Node *root,*q[N];
Node* newnode()
{
Node *u;
u = (Node*)malloc(sizeof(Node));
if(u!=NULL)
{
u->flag = 0;
u->left = u->right = NULL;//初始时没有左右儿子
}
return u;
}
int addnode(int v,char *str)
{
int l = strlen(str);
Node *u = root;
for(int i = 0; i < l; i ++)//根结点开始往下走
{
if(str[i] == ‘L‘)
{
if(u->left == NULL)
u->left = newnode();//结点不存在，建立新结点
u = u->left ;//往左走
}
else if(str[i] == ‘R‘)
{
if(u->right == NULL)
u->right = newnode();
u = u->right ;
}
}
if(u->flag)//如果最后结束的括号也被标记为用过了，说明输入有误
failed = 1;
u->number = v;
u->flag = 1;//标记为已经用过
return 1;
}
void read_input()
{
root = newnode();//创建根结点
failed = 0;//记录输入是否有误
while(scanf("%s",s),strcmp(s,"()")!=0)
{
sscanf(&s[1],"%d",&v);//读入结点值
addnode(v,strchr(s,‘,‘)+1);//查找逗号,然后插入结点
}
return ;
}
int bfs()
{
int front = 0,rear = 1,v;
q[0] = root;//初始时只有一个根结点
n = 0;
while(front < rear)
{
Node* u = q[front++];
if(!u->flag)
return 0;//有结点没有被赋值过，表明输入有误
ans[n++] = u->number ;//增加到输出序列尾部
if(u->left != NULL)
q[rear++] = u->left ;//如果有，把左儿子放进队列
if(u->right != NULL)
q[rear++] = u->right ;//把右儿子放进队列
}
return 1;
}
int main()
{
read_input();
if(failed||!bfs())
printf("-1\n");
else
{
for(int i = 0; i < n-1; i ++)
printf("%d ",ans[i]);
printf("%d\n",ans[n-1]);
}
return 0;
}
第六章例题二叉树层次遍历
1.指针实现#include<iostream>#include<vector>#include<queue>#include<cstdio>#include<cstring>usingnamespacestd;#definemaxn100structNode{boolhave_value;intvalue;/*节点结构体*/ 查看详情
数据结构与算法(周鹏-未出版)-第六章树-习题
①二叉树是不是树的特殊情况？答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。②：满二叉树和完全二叉树有什么区别... 查看详情
数据结构与算法(周鹏-未出版)-第六章树-6.3二叉树基本操作的实现
6.3二叉树基本操作的实现 二叉树的基本操作在6.2.1小节中已经定义，在这些操作中有一组非常重要的操作就是遍历操作，下面首先介绍遍历及其实现，然后介绍其他操作的实现。 在以下操作的实现中涉及了实现二叉树的B... 查看详情
数据结构二叉树经典入门算法题集锦（下）(代码片段)
前言：本章将通过五道来自LeetCode/牛客网中的二叉树相关算法题来介绍数据结构中二叉树在算法题中的应用，题目难度不大，大家就当放松放松。文章目录1.二叉树的最大深度思路分析：题解：2.平衡二叉树思... 查看详情
数据结构二叉树经典入门算法题集锦(代码片段)
前言：本章将通过六道来自LeetCode/牛客网中的二叉树相关算法题来介绍数据结构中二叉树在算法题中的应用。文章目录1.单值二叉树思路分析：题解：2.二叉树的前序遍历思路分析：题解：3.相同的树思路分析&#... 查看详情
.数据结构与算法基础(代码片段)
目录第六章.数据结构与算法基础（重点）第一节.数组与矩阵数组稀疏矩阵第二节.数据结构的定义第三节.线性表链表详解顺序存储与链式存储对比队列与栈第四节.广义表第五节.树与二叉树树的概念二叉树的分类二叉树... 查看详情
第六章树和二叉树
数据结构与算法(周鹏-未出版)-第六章树-6.4树森林
6.4树、森林在介绍二叉树之后，我们回到树的存储及其操作的实现中来。6.4.1树的存储结构树的存储结构主要有以下三种。[email protected]双亲表示法设T是一棵树，表示T的一种最简单的方法是用一个一维数组存储每个结点，数... 查看详情
算法入门经典第六章例题6-5移动盒子
例题6-5移动盒子（BoxesinaLine,UVa127675）问题给定一行盒子，从左到右编号依次为1，2，...，n.可以执行以下命令：1XY 把盒子X移动到Y的左边（如果已经在左边，忽略此命令）2XY 把盒子X移动到Y右边（如果X已经在Y的右边，忽... 查看详情
数据结构与算法(周鹏-未出版)-第六章树-6.1树的定义及基本术语
第六章树目录6.1树的定义及基本术语6.2二叉树6.3二叉树基本操作的实现6.4树、森林6.5Huffman树 前面我们介绍了线性表、栈和队列，这些数据结构都是线性结构，在本章中我们介绍一种重要的非线性结构——树。在第二章曾经... 查看详情
算法入门经典第六章例题6-15给任务排序
假设有n个变量，还有m个二元组（u，v），分别表示变量u小于v。那么，所有变量从小到大排列起来应该是什么样子呢？例如，有4个变量a,b,c,d,若已知a<b,c<b,d<c,则这4个变量的排序可能是a<d<c<b。尽管还有其他可能... 查看详情
数据结构与算法(周鹏-未出版)-第六章树-6.5huffman树
6.5Huffman树 Huffman树又称最优树，可以用来构造最优编码，用于信息传输、数据压缩等方面，是一类有着广泛应用的二叉树。6.5.1二叉编码树 在计算机系统中，符号数据在处理之前首先需要对符号进行二进制编码。例如，... 查看详情
算法入门经典第六章例题6-14abbott的复仇(abbott'srevenge)bfs算法实现
SampleInput31N33 11WLNR* 12WLFNRER* 13NLER* 21SLWRNF* 22SLWFELF* 23SFREL* 0SampleOutput(3,1)(2,1)(1,1)(1,2)(2,2)(2,3)(1,3)(1,2)(1,1)(2,1) (2,2)(1,2)(1,3)( 查看详情
算法竞赛入门经典_6数据结构基础
*6.3 树和二叉树**小球下落问题 //小球下落问题/*有一棵二叉树,最大深度为D,且所有叶子的深度相同.所有节点从上到下从左到右编号为1,2,3,4,...,2^D-1.在节点1处放一小球,它会往下落.每个内节点上都有一个开关,初始全部关闭... 查看详情
《码出高效java开发手册》第六章数据结构与集合
码云:https://gitee.com/forxiaoming/JavaBaseCode/blob/master/EasyCoding/src/collection/index.md6.1数据结构1.数据结构定义:数据结构是指逻辑意义上的数据组织方式及其相应的处理方式;1.1.数据组织方式:树:二叉树,三叉树,B+树等;图:有向图,无向图;队列... 查看详情
6.3.3二叉树重建算法入门经典双十一大礼包
输入一棵二叉树的先序遍历和中序遍历，输出它的后序遍历序列。运行如图目前还有一些细节没有懂，不过不影响我仍然喜欢学习的心情~#include<stdio.h>#include<string.h>#defineN1000chars1[N],s2[N],ans[N];//s1是先序遍历,s2是中序遍历... 查看详情
数据结构与算法:树二叉树入门(代码片段)
...列介绍的是数据结构:树这是第一篇目前计划一共有12篇:二叉树入门(本篇)顺序二叉树线索化二叉树堆排序赫夫曼树(一)赫夫曼树(二)赫夫曼树(三)二叉排序树平衡二叉树2-3树,2-3-4树,B树B+树B*树了解红黑树(一)红黑树(二)敬请期待... 查看详情
一文通数据结构与算法之——二叉树+常见题型与解题策略+leetcode经典题(代码片段)
文章目录二叉树1二叉树基本操作1.1二叉树定义1.2前、中、后序遍历1.2.1递归形式1.2.2非递归，迭代形式1.3遍历方式2剑指Offer算法题2.1题目列表递归遍历序列化和反序列化二叉搜索树2.2实战[剑指Offer27.二叉树的镜像](https://leetcod... 查看详情