笔试常考题型之二叉树的遍历

一、介绍

在互联网公司的笔试题中,经常会出现给出一个二叉树的前序和中序遍历,让你去求它的后序遍历问题,因此我将这类题型的解题步骤总结如下。

二、例题

题目解析:

注:此题中f节点的爸爸是d。

前序遍历顺序 根->左->右:abefd。

中序遍历顺序 左->根->右:ebadf。

后序遍历顺序 左->右->根:ebfda。

题目解析:

二叉搜索树有一个很重要的特性:树中任何结点的左子树中所有结点的值均比该结点小,右子树中所有结点的值均比该结点大。对二叉搜索树进行中序遍历即得到一个递增排序的序列。

因此,检查一个树是否是二叉搜索树可以使用中序遍历,根据递增排序的序列生成二权搜索树也可以使用中序遍历。

参考资料:二叉搜索树的简单介绍 二叉排序_搜索_查找树 C++

题目解析:

1,先序遍历的第一个节点肯定是根节点,所以A为该二叉树的根节点。

2,中序遍历中根节点左侧的节点全是根节点左子树的节点,根节点右侧的节点全是根节点的右子树。所以我们可以分成 DCB(左) | A(根) | EFG(右)。

3,递归使用上述两个步骤,可以画出整个二叉树。

(1)先得出A是根节点。

(2)DCB是A左子树中的点,EFG是A右子树中的点。

(1)B是A左子树的根节点,E是A右子树的根节点。

(2)CD是B左子树中的点,FG是E右子树中的点。

(1)C是B左子树的根节点,F是E右子树的根节点。

(2)D是C左子树中的点,G是F右子树中的点。

因此该二叉树的后序遍历为(左->右->根):DCBGFEA。

三、解题感受

遇到这种问题,记得先找出根节点,然后找出根节点左边的节点和根节点右边的节点,然后以此类推,找出根节点左子树的根节点和右子树的根节点...最后可以根据前序和中序遍历画出一个二叉树,再根据画出的二叉树(前提是要保证之前的步骤都正确)求出后序遍历。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android相关

二叉查找树(Binary Search Tree)

在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜...

34430
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

19240
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

831110
来自专栏琯琯博客

PHP二叉树(一):平衡二叉树(AVL)

平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

39590
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1.4K20
来自专栏书山有路勤为径

二叉查找树

二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

6620
来自专栏null的专栏

数据结构和算法——二叉树

二叉树是使用较多的一种树形结构,如比较经典的二叉排序树,Huffman编码等,都使用到了二叉树的结构,同时,在机器学习算法中,基于树的学习算法中也大量使用到二叉...

31850
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

15830
来自专栏mathor

二叉树的下一个结点&二叉树的上一个结点

 最笨的方法就是一直网上回溯,直到找到了头结点,然后从头结点开始重新中序遍历一次树,然后得到答案  还有一种比较巧妙的方法,先判断当前结点有没有右子树,如果有...

7220
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

12120

扫码关注云+社区

领取腾讯云代金券