专栏首页开发 & 算法杂谈前序遍历中序遍历求后序遍历-数组篇

前序遍历中序遍历求后序遍历-数组篇

有关树的相关概念就不再这里介绍了,不清楚的同学可以自己查看。

如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

但是假设我们的遍历顺序存放在数组中,那么我们大可不必那么麻烦。下面就是针对数组求后序遍历的算法,代码如下,大家供参考。

#include <stdio.h>

//前序遍历:根左右
//中序遍历:左根右
//后序遍历:左右根

//在前序遍历和中序遍历的基础上,我们从前序遍历中找出根节点,然后从中序遍历中找出根节点的左右分支
//这里由于我们是通过数组来存放的,因此有一点肯定的是根节点左右的分值都是连续存在数组中的
//因此我们这里选择的是分值在数组中的首地址,以及分值的个数作为参数
void postorder(int a[],int b[],int len)
{
	if(len==0) //不存在节点
		return ;
	else if(len==1) { //存在一个节点
		printf("%d ",a[0]);
		return ;
	}
	//在b中搜索根节点的位置
	int i;
	for(i=0;i<len;i++)
		if(b[i]==a[0])
			break;
	//左分值
	postorder(a+1,b,i);
	//右分支
	postorder(a+i+1,b+i+1,len-i-1);
	//打印根节点
	printf("%d ",a[0]);
}

int main()
{
	int a[6]={1,2,4,3,5,6};
	int b[6]={4,2,1,5,3,6};
	postorder(a,b,6);
	return 0;
}

结果如下所示:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 较快速在一个数组中查找最大值和最小值(2)

    chain
  • Ad-hoc类型同步识别

    尽管之前的我们提出的动态数据竞争验证和检测方法能够比较精确地找到数据竞争,但是该方法还是会存在一部分误检,误检主要就是由于ad-hoc类型的同步引起的,下图展示...

    chain
  • django 实现未经登录验证的url过滤

    本人在做一个基于sae的在线学习系统,语言使用的python,web框架用的是django1.4。

    chain
  • 5.2二叉搜索树遍历(前序、中序、后序、层次、广度优先遍历)

    前言:在上一节中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树。

    wfaceboss
  • 图的深度遍历和广度遍历

    图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的...

    233333
  • 遍历

    前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    Centy Zhao
  • 爬虫课程(四)|深度优先和广度优先算法

    黄小怪
  • 【图解数据结构】 一组动画彻底理解二叉树遍历

    定义:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    五分钟学算法
  • LeetCode | 100.相同的树

    上面的题就是 相同的树 题目的截图,同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义,然后在其中实现 相同的树 的解题过程。这次我使用 ...

    码农UP2U
  • 如何根据二叉树的两种遍历方式重建二叉树(理论篇)

    我们知道,二叉树有三种不同的遍历方式:先序遍历,中序遍历和后序遍历。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就...

    青南

扫码关注云+社区

领取腾讯云代金券