专栏首页CSDN搜“看,未来”二叉树的前中后序遍历

二叉树的前中后序遍历

这篇主要是放这里提醒自己这些基础算法要能用白纸手写出来。

讲遍历之前我先找找以前有没有画树的图拿来用一下。

太好了,有啊,下面就统一用这张图:

最左下角那个是“H”啊,小了点。

前序遍历

前序遍历主要思想是什么呢?从根节点开始,前序遍历访问左子树,遇到空节点则返回,然后再前序遍历访问右子树,遇到空节点则返回。

说的会比较抽象一点,直接看: 对上图进行前序遍历,结果为: A B D H I E J K C F L G

当然,也可以直接看代码:

虽然是我现场手写,不过我有信心不会错啊

void PreOrderTraverse(Tree T)
{
	if(T == NULL)
		return;
	
	cout<<T.data;	//打印节点信息
	PreOrderTraverse(T->leftChild);	//这一步会一直走到没有左儿子为止
	PreOrderTraverse(T->rightChild);	//没有左儿子就去看一眼右儿子,顺便看看有没有左外孙
	//如果都没有,那就跳回到他爸,让他爸去找他弟弟
}

我已经写的这么通俗易懂了,我日后要是自己看不懂,那我就是二货。

当然,如果学习过进程和线程会比较好想象个中奥妙。

中序遍历

中序遍历主要思想是什么呢?从根节点开始,中序遍历左子树,遇到空节点则返回后访问,然后再中序遍历右子树,遇到空节点则返回后访问。

我也不想绕弯子,省的到时候我自己都看不懂是什么东西了。 前序遍历和中序遍历的差别就在于什么时候访问。后序遍历也是一个德行。

看代码,其实差别也很细微。

void MidOrderTraverse(Tree T)
{
	if(T == NULL)
		return;
	
	MidOrderTraverse(T->leftChild);	//这一步会一直走到没有左儿子为止
	cout<<T.data;	//打印节点信息		//也就这行换到这里
	MidOrderTraverse(T->rightChild);	//没有左儿子就去看一眼右儿子,顺便看看有没有左外孙
	//如果都没有,那就跳回到他爸,让他爸去找他弟弟
}

所以中序遍历的顺序是: H D I B J E K A L F C G

后续遍历

后续遍历更加不废话了,直接上代码好了:

void LastOrderTraverse(Tree T)
{
	if(T == NULL)
		return;
	
	LastOrderTraverse(T->leftChild);	//这一步会一直走到没有左儿子为止
	LastOrderTraverse(T->rightChild);	//没有左儿子就去看一眼右儿子,顺便看看有没有左外孙
	cout<<T.data;	//打印节点信息		//也就这行换到这里
}

顺序:H I D J K E B L F G C A

注:

如果对于以上顺序有疑义,可以自己一步一步画出来,画完还有疑义,可以在下面评论咱一起讨论讨论。

已知遍历排序求树

数据结构考试就喜欢考这种题目。 首先要明确:那棵树,肯定是二叉树。 然后我们来分析。

前序:A B D H I E J K C F L G 中序:H D I B J E K A L F C G 后序:H I D J K E B L F G C A

一般不会给你三个,也不会只给一个,还没那么小气哈。 不管给哪两个,来分析一下:

首先肯定要把根节点找出来,明眼人一看就知道是A,别问我为什么。

接下来分三种情况来讨论:

  1. 如果给了前、中序排列
//给了中序那就好办了
//一:看中序排列中的根节点位置在哪里,根节点前面都属于根的左子树及其后代,后面你懂得。
//二:将中序序列分两段:(H、D、I、B、J、E、K)和(L、F、C、G)
//三:明眼人一看就知道根节点左子树的“根节点”是:B
//别问我为啥,问就是看前序序列的第二位
//四:重复二三,直到根节点左子树排出来为止
//五:同上,排出右子树

如果觉得看不懂,自己动手试一下。

  1. 如果给了后、中序排列
//一、二步同上
//其实第三步原理是一样的,不过我们的脑子习惯了从前到后,所以,让我帮你们转个弯。

//像对中序分割一样,将后序序列也分割了。
//从中序排列的分割中我们知道根节点的右子树有哪些成员,所以后序序列这样分:
//(H I D J K E B)(L F G C)
//现在就很明显可以看出根节点左子树的“根节点”是谁了吧

//重复以上步骤

还是那句话,要是觉得晕,自己操作一遍。

  1. 如果给了前后序序列

这个书上说不行,我也曾自己想了个方法来想推翻这个结论,即前序的第n个数不等于后序的倒数第n个数,则前序的那第n个数必定是当前节点的左子节点,然后将序列截开,截开方式和上面一样不多说。 但是后来发现,上面那个结论是没错,但那只是一半,它的令一半没办法,即前序的第n个数等于后序的倒数第n个数,那就麻烦了,因为并不能武断的说当前节点那就没有左子节点,第n个数就是右节点。

通过一个简单的反例便可以推翻: 一颗歪脖子树,有节点 A B C D,一路向左。那么前序遍历就是ABCD,后序遍历就是DCBA,按照我原先的想法,前序的第二个数是B,后序的第二个数也是B,那这时候怎么办,B会是A的右子节点?显然不是。

然后我右深入想了一下,如果A B C D,一路向右,它的前序也是ABCD,它的后序依旧DCBA,和一路向左一样啊!!!

由此得出结论,如果是给了前后序序列,那是真的不行。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 浅谈多路查找树(B树)

    曾今我不知道多叉树有上面用,所以对于多叉树并没有过多的关注,或者说,基本没关注。 直到我了解到了多路查找树(B树),我知道,是我浅薄了。

    看、未来
  • 拥抱STL -树的导览

    树,一种十分基础的数据结构。 本篇将重点讲一些树的基础知识,作为下一篇《走进STL - 红黑树》的支持。

    看、未来
  • 【回溯算法】N叉树相关技巧

    二叉树是一棵以根节点开始,每个节点含有不超过 2 个子节点的树。让我们将这个定义扩展到 N 叉树 。 一棵以根节点开始,每个节点不超过 N 个子节点的树,称为 ...

    看、未来
  • 数据结构+算法(第15篇):“神之一着”与“翻云手”!后序遍历还能这么玩

    《精通二叉树的“独门忍术”——线索二叉树(上)》和《精通二叉树的“独门忍术”——线索二叉树(中)》分别介绍了非递归的、不使用堆栈的、空间复杂度为O(1)的中序遍...

    用户5224393
  • 数据结构 非线性结构

    节点 父节点 子节点 子孙 祖先 堂兄弟 深度:从根节点到最底层节点的层数。(根节点是第一层) 叶子节点:没有子节点的节点 非终端节点:实际就是...

    Debug客栈
  • 如何根据二叉树的两种遍历方式重建二叉树(理论篇)

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

    青南
  • dfs

    Mister24
  • 二叉树---(3)前序遍历,中序遍历,后序遍历

            很多朋友在刚开始接触二叉树时,对前序遍历,中序遍历,后序遍历这三个遍历方式不太了解,很多博客中,上来就是实现方式,并没有清晰的阐述这三种遍历的步...

    IT云清
  • 二叉树的遍历回顾

    本文重点在于复习并总结 二叉树每种遍历方式的递归与迭代实现,图片和示例代码均来自《邓俊辉-数据结构》。

    李拜六不开鑫
  • 一天一大 lee(二叉树的中序遍历)难度:中等-Day20200914

    递归方法采用了深度优先遍历的形式,一般可以采用深度优先遍历就可以采用广度优先遍历。

    前端小书童

扫码关注云+社区

领取腾讯云代金券