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

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法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。

目录
相关文章
|
25天前
|
存储 JavaScript 前端开发
JavaScript中的对象是数据结构,存储键值对,键为字符串,值可为任意类型,包括函数(作为方法)
【6月更文挑战第25天】JavaScript中的对象是数据结构,存储键值对,键为字符串,值可为任意类型,包括函数(作为方法)。
24 2
|
24天前
|
存储 自然语言处理 NoSQL
深入解析Elasticsearch的内部数据结构和机制:行存储、列存储与倒排索引之倒排索引(三)
深入解析Elasticsearch的内部数据结构和机制:行存储、列存储与倒排索引之倒排索引(三)
|
24天前
|
存储 自然语言处理 NoSQL
深入解析Elasticsearch的内部数据结构和机制:行存储、列存储与倒排索引之列存(二)
深入解析Elasticsearch的内部数据结构和机制:行存储、列存储与倒排索引之列存(二)
|
24天前
|
存储 JSON NoSQL
深入解析Elasticsearch的内部数据结构和机制:行存储、列存储与倒排索引之行存(一)
深入解析Elasticsearch的内部数据结构和机制:行存储、列存储与倒排索引之行存(一)
|
25天前
|
搜索推荐 算法 大数据
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
|
26天前
|
编译器 数据库 索引
数据结构篇:树形数据结构的基本概念及其遍历方法
数据结构篇:树形数据结构的基本概念及其遍历方法
9 0
|
1月前
|
XML Java 数据格式
深度解析 Spring 源码:从 BeanDefinition 源码探索 Bean 的本质
深度解析 Spring 源码:从 BeanDefinition 源码探索 Bean 的本质
32 3
|
16天前
|
存储 安全 Java
深度长文解析SpringWebFlux响应式框架15个核心组件源码
以上是Spring WebFlux 框架核心组件的全部介绍了,希望可以帮助你全面深入的理解 WebFlux的原理,关注【威哥爱编程】,主页里可查看V哥每天更新的原创技术内容,让我们一起成长。
|
17天前
|
关系型数据库 分布式数据库 数据库
PolarDB-X源码解析:揭秘分布式事务处理
【7月更文挑战第3天】**PolarDB-X源码解析:揭秘分布式事务处理** PolarDB-X,应对大规模分布式事务挑战,基于2PC协议确保ACID特性。通过预提交和提交阶段保证原子性与一致性,使用一致性快照隔离和乐观锁减少冲突,结合故障恢复机制确保高可用。源码中的事务管理逻辑展现了优化的分布式事务处理流程,为开发者提供了洞察分布式数据库核心技术的窗口。随着开源社区的发展,更多创新实践将促进数据库技术进步。
21 3
|
1月前
|
XML Java 数据格式
深度解析 Spring 源码:揭秘 BeanFactory 之谜
深度解析 Spring 源码:揭秘 BeanFactory 之谜
23 1

推荐镜像

更多