目录
题目描述
输入示例
输出示例
解题思路
解题方法(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。
文章来源:https://www.toymoban.com/news/detail-468473.html
文章来源地址https://www.toymoban.com/news/detail-468473.html
到了这里,关于数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!