数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)

这篇具有很好参考价值的文章主要介绍了数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目描述

输入示例

输出示例

解题思路 

解题方法(C语言)

解析


题目描述

有序的二叉树遍历可以用堆栈以非递归的方式实现。

例如:

假设遍历一个节点数为6的二叉树(节点数据分别为1到6)时,

堆栈操作为:push(1);push(2);push(3);pop();pop();push(4);pop();pop();push(5);push(6);pop();pop()。

外面可以根据这一操作序列生成一个唯一的二叉树。

我们的任务就是根据给出的操作序列求出该树的后序遍历序列;

换句话说,就是我们之前学习过的,根据给出先序遍历和中序遍历求出该树的后序遍历序列。

输入示例

第一行包含一个正整数N(≤30),它表示树中节点的总数。

接下来的2N行,每行描述一个堆栈操作,

格式为:“Push X”,其中X是被入到堆栈上的节点;

或“Pop”,意思是从堆栈中弹出一个节点。

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

输出示例

对于每个测试用例,在一行中打印相应树的后序遍历序列。

所有数字必须用一个空格隔开,并且行的末尾不能有多余的空格。

3 4 2 6 5 1

解题思路 

解这道题的思路并不难,我们之前就学习过通过两种遍历序列(其中一种为中序序列)就可以确定一颗唯一确定的二叉树,进而得到其余的遍历序列。即先序遍历序列中,第一个节点为根节点;后序遍历序列中,最后一个节点为根节点;中序遍历序列中根节点左右的序列分别是其左右子树的节点。

​​​​​​二叉树的遍历 习题

解题方法(C语言)

void solve(int preL, int inL, int postL, int n)
{
	if(n == 0)
	{
		return;
	}
	if(n == 1)
	{
		post[postL] = pre[preL];
		return;
	}
	root = pre[preL];
	post[postL + n - 1] = root;
	for (i = 0; i < n; i++)
	{
		if (in[inL + i] == root)
			break;
	}
	L = i;
	R = n - L - 1;
	solve(preL + 1, inL, postL, L);
	solve(preL + L + 1, inL + L + 1, postL + L, R);
}

解析

首先讲一下各变量的含义:

root表示当前子树的根节点;

pre表示先序遍历序列;

post表示后序遍历序列;

in表示中序遍历序列;

L表示当前子树的左子树节点个数;

R表示当前子树的右子树节点个数。

序列我们当成一个数组

preL表示当前子树在先序遍历序列中的起始位置的下标;

inL表示当前子树在中序遍历序列中的起始位置的下标;

postL表示当前子树在后序遍历序列中的起始位置的下标;

n表示当前子树的节点个数。

函数的流程:

如果当前子树节点个数为0,则直接返回,没有后序遍历序列;

如果当前子树节点个数为1,则将该节点加入到后序遍历序列中,并返回;

如果当前子树节点个数大于1,则取出当前子树的根节点root,(即先序遍历序列的第一个元素)

将其加入到后序遍历序列的最后一个位置;(后序遍历序列中,最后一个元素为根节点)

然后在中序遍历序列中找到root的位置,将其左边的节点个数记为L,右边的节点个数记为R;

最后就是两个递归:

递归处理左子树,起始位置分别为preL+1、inL、postL,节点个数为L;

递归处理右子树,起始位置分别为preL+L+1、inL+L+1、postL+L,节点个数为R。

数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)

 文章来源地址https://www.toymoban.com/news/detail-468473.html

到了这里,关于数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • B_Tree 的数据结构

    头文件(结构体定义与函数声明): 函数实现 (需要在源文件即后缀为.c的文件中实现,否则编译器会报错,重复定义函数): 最后在main源文件中只需要包含该头文件即可使用定义的抽象数据类型: 这里没有提供具体样例,可根据实际情况自行编写。

    2024年01月17日
    浏览(39)
  • 022:vue中tree结构数据变成扁平化table结构数据的示例

    第022个 查看专栏目录: VUE ------ element UI 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 (1)提供vue2的一些基本操作:安装、引用,模板使用,computed,watch,生命周期(beforeCreate,created,beforeMount,mounted, beforeUpdate,upda

    2024年02月12日
    浏览(43)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(40)
  • 【数据结构基础】树 - 前缀树(Trie Tree)

    Trie,又称字典树、单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的

    2024年02月07日
    浏览(43)
  • 第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频)

    注:笔记截图均来自王卓数据结构教学视频 线性表是具有相同特性的数据元素的一个有限序列 同一线性表中的元素必定具有相同特性,数据元素间的关系是线性关系。 稀疏多项式的运算 顺序存储结构存在的问题 1、存储空间分配不灵活 2、运算的空间复杂度高 引出链式存储

    2024年02月15日
    浏览(38)
  • 第一百零六天学习记录:数据结构与算法基础:单链表(王卓教学视频)

    结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻 线性表的链式表示又称为非顺序映像或链式映像。 用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意

    2024年02月16日
    浏览(54)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • 红黑树下岗,内核新数据结构上场:maple tree!

      在外界看来,Linux 内核的内部似乎变化很少,尤其是像内存管理子系统(memory-management subsystem)这样的子系统。然而,开发人员时常需要更换内部接口来解决某些长期存在的问题。比如,其中一个问题就是用来保护内存管理里的重要结构的锁的竞争问题,这些重要结构是指

    2024年02月04日
    浏览(48)
  • 数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)

    目录 邻接矩阵 图节点的结构 创建并初始化 插入边 完整的图的建立  邻接表 图节点的结构 创建并初始化 插入边  完整的图的建立  定义结构体GNode,其中包含以下成员变量: Nv:表示图中的顶点数。 Ne:表示图中的边数。 二维数组表示图的邻接矩阵。它的大小是MaxVertexN

    2024年02月06日
    浏览(46)
  • Element-UI控件Tree实现数据树形结构

            在前端开发中,有时会遇到所有菜单数据在同一级的情况,后端未对数据进行分级处理;但前端渲染需要是树状结构的数据,如何实现数据的树状化?将数组中通过父节点的ID与子节点的parentId关联,通过递归函数来实现。         前端框架这里使用element-ui的tree控件

    2024年02月05日
    浏览(118)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包