算法通关村第六关——如何使用中序和后序来恢复一颗二叉树

这篇具有很好参考价值的文章主要介绍了算法通关村第六关——如何使用中序和后序来恢复一颗二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 树的基础知识

1.1 树的定义

树(Tree):表现得是一种层次关系,为 n ( n ≥ 0 ) n(n≥0) nn0个节点构成的有限集合,当n=0时,称为空树,对于任一颗非空树(n>0),它具备以下性质:

  • ​ 树中有一个根(root)节点,用r表示

  • ​ 其余节点可分为m(m>0)互不相交的有限集 T 1 , T 2 , . . . , T m \bold{T_1,T_2, ...,T_m} T1,T2,...,Tm ,其中每个集合本身又是一棵树,称为原来树的子树(Subtree)。子树不相交;除了根结点外,每个结点有且仅有一个父结点;一颗N个结点的树有N-1条边。

树的一些基本术语

  1. 结点的度(Degree):结点的子树个数
  2. 树的度:树的所有结点中最大的度数
  3. 叶结点(Leaf):度为0的结点
  4. 父结点(Parent):有子树的结点是其子树的根节点的父结点
  5. 子结点(Child):若A结点是B结点的父结点,则称B结点是A结点的子结点;子结点也称孩子结点。
  6. 兄弟结点(Sibling):具有同一父结点的各结点是彼此的兄弟结点。
  7. 路径和路径长度:从结点 n 1 n_1 n1 n x n_x nx的路径为一个结点序列 n , n 2 , . . . , n x n,n_2 ,... , n_x n,n2,...,nx , n i n_i ni n i + 1 n_{i+1} ni+1 的父结点。路径所包含边的个数为路径的长度
  8. 祖先结点(Ancestor):沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
  9. 子孙结点(Descendant):某一结点的子树中的所有结点是这个结点的子孙。
  10. 结点的层次(Level):规定根结点在1层,其它任一结点的层数是其父结点的层数加1。
  11. 树的深度( Depth):树中所有结点中的最大层次是这棵树的深度。
  12. 森林:由m(m > 0)棵互不相交的树的集合称为森林。
  13. 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树也称为自由树。
  14. 有序树:树中任意节点之间有顺序关系,这种树称为有序树;
  15. 二叉树:每个结点最多含有两个子树的树称为二叉树

1.2 树的性质

  1. 一个二叉树第i层的最大结点数为: 2 i − 1 , i ≥ 1 2^{i-1},i≥1 2i1,i1

  2. 深度为k的二叉树有最大结点总数为: 2 k − 1 , k ≥ 1 2^k-1,k≥1 2k1,k1

  3. 对任何非空二叉树 T T T ,若 n 0 n_0 n0 表示叶结点的个数, n 2 n_2 n2 是度为2的非叶结点个数,那么两者满足关系 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1

  4. 具有n个结点的完全二叉树的深度必为 l o g 2 ( n + 1 ) log_2(n+1) log2(n+1)

  5. 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为 i 2 \frac{i}{2} 2ii=1 时为根,除外)

    对二叉树的重要操作:主要是遍历

满二叉树:如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。

算法通关村第六关——如何使用中序和后序来恢复一颗二叉树,算法,算法,数据结构

完全二叉树:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大 值,并且最下面一层的节点都集中在该层最左边的若干位置。
算法通关村第六关——如何使用中序和后序来恢复一颗二叉树,算法,算法,数据结构

1.3 树的存储方式

  • 顺序存储结构

    • ​ 完全二叉树:按从上至下、从左到右顺序结构

算法通关村第六关——如何使用中序和后序来恢复一颗二叉树,算法,算法,数据结构

  • 链表存储

算法通关村第六关——如何使用中序和后序来恢复一颗二叉树,算法,算法,数据结构

1.4 树的遍历方式

  • 深度优先遍历:先往深走,遇到叶子节点再往回走。
    • 前序遍历(中左右)
    • 中序遍历(左中右)
    • 后序遍历(左右中)

算法通关村第六关——如何使用中序和后序来恢复一颗二叉树,算法,算法,数据结构

  • 广度优先遍历(层次遍历):一层一层的去遍历,一层访问完再访问下一层。

2 通过序列构造二叉树

2.1 根据后中序列复原二叉树

给定三个序列:

(1) 前序:1 2 3 4 5 6 8 7 9 10 11 12 13 15 14

(2) 中序:3 4 8 6 7 5 2 1 10 9 11 15 13 14 12

(3) 后序:8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

分析

根据后序和中序遍历来复原二叉树的思路就是先根据后序遍历确定根节点,然后中序遍历中根节点左边的是左子树,根节点右边的是右子树。根据中序遍历划分好的左右子树,在后序遍历里划分好左右子树。我们知道后序遍历最后遍历中间结点,那么就可以在后序遍历里划分好的左右子树中确定左右子树的根节点,再返回中序遍历划分左右子树。以此类推,直到复原二叉树。

第一轮:
中: 3 4 8 6 7 5 2 | 10 9 11 15 13 14 12

后: 8 7 6 5 4 3 2 | 10 15 14 13 12 11 9


第二轮:
中: 3 4 8 6 7 5 | null	    10 | 11 15 13 14 12

后: 8 7 6 5 4 3 | null		10 | 15 14 13 12 11


第三轮:
中:null | 4 8 6 7 5		null | 15 13 14 12

后:null | 8 7 6 5 4 	    null | 15 14 13 12


第四轮:
中:null | 8 6 7 5        15 13 14 | null

后:null | 8 7 6 5		15 14 13 | null


第五轮:
中: 8 6 7 | null			15 | 14

后: 8 7 6 | null


第六轮:
中: 8 | 7		

复原后的二叉树:

算法通关村第六关——如何使用中序和后序来恢复一颗二叉树,算法,算法,数据结构

2.2 根据前中序列复原二叉树

分析

根据前序遍历和中序遍历来复原二叉树,与根据后序遍历和中序遍历复原二叉树不同之处在于前序遍历先遍历根结点,再遍历左右结点。先根据前序遍历找到根结点,再在中序遍历中划分左右子树,之后根据中序遍历划分的左右子树来对前序遍历的左右子树进行划分,之后再找左右子树的根结点。以此类推,直到复原。

过程不再赘述,与根据后序遍历和中序遍历复原二叉树大同小异。文章来源地址https://www.toymoban.com/news/detail-636304.html

到了这里,关于算法通关村第六关——如何使用中序和后序来恢复一颗二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村第九关——中序遍历与搜索树

    二叉搜索树按照中序遍历正好是一个递增序列。其比较规范的定义是: 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不为空,则右子树所有节点的值均大于它的根节点的值; 它的左、右子树也分别为二叉搜索树,比如下面的例子:

    2024年02月11日
    浏览(36)
  • 力扣-根据前序和后序遍历构造二叉树(java)

    原题链接: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/ 题目描述: 给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,postorder 是同一棵树的后序遍历,重构并返回二叉树。 如果存在多个答案,您可以返回

    2024年02月08日
    浏览(46)
  • 【2023】字节跳动 10 日心动计划——第六关

    🔗 原题链接:142. 环形链表 II 用哈希表判重即可。 🔗 原题链接:LCR 070. 有序数组中的单一元素 这里介绍两种做法。 方法一:异或。注意到 x ⊕ x = 0 xoplus x=0 x ⊕ x = 0 ,因此 ⊕ i = 1 n n u m s [ i ] oplus_{i=1}^nnums[i] ⊕ i = 1 n ​ n u m s [ i ] 就是最终答案。 方法二:二分。注意到

    2024年02月14日
    浏览(38)
  • Java根据二叉树的先序和后序得到二叉树

    一般情况下,我们会根据先序和后序写出二叉树,但是用代码怎末写呢? 例如: 给定两个整数数组  preorder  和  inorder  ,其中  preorder  是二叉树的 先序遍历 ,  inorder  是同一棵树的 中序遍历 ,请构造二叉树并返回其根节点。 思路:我们先根据先序遍历找到根节点记录

    2024年01月19日
    浏览(38)
  • 递归和迭代实现二叉树先序、中序、后序和层序遍历

    递归比较简单,直接上代码: ### 1.1 先序遍历 1.2 中序遍历 1.3 后序遍历 能够用递归方法解决的问题基本都能用非递归方法实现。因为递归方法无非是利用函数栈来保存信息,可以寻找相应的数据结构替代函数栈,同样可以实现相同的功能。下面用栈,类比递归方法来统一实

    2024年01月20日
    浏览(41)
  • 7-1 根据后序和中序遍历输出先序遍历 (PTA-数据结构)

    本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以空格分隔。题目保证输入正确对应一棵二叉树。 输出

    2024年02月03日
    浏览(44)
  • 编程导航算法通关村第 1 关|青铜 - C++是如何构造出链表的

             在C++中,链表是由一系列节点构成的,每个节点包含一个值和一个指向下一个节点的指针。         我们可以用结构体定义出一个节点:               在定义完后,我们将链表进行初始化,并插入5条数据:   接着我们在主函数中进行测试,看看是否能成

    2024年02月13日
    浏览(41)
  • 初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)

    本篇博客是初阶数据结构树的收尾,将会讲掉 基本二叉树链式结构的具体内容和实现,包括二叉树的构建,前序遍历,中序遍历,后序遍历和层序遍历,计算二叉树结点个数,第k层结点个数,二叉树叶子结点个数,以及判断一个二叉树是否为完全二叉树 。话不多说,开始我

    2024年03月24日
    浏览(51)
  • 贪心算法|53.最大子序和

    力扣题目链接 这题的暴力解法很好理解,以上是贪心解法的代码。 贪心解法 贪心贪的是哪里呢? 如果 -2 1 在一起,计算起点的时候,一定是从 1 开始计算,因为负数只会拉低总和,这就是贪心贪的地方! 局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重

    2024年04月09日
    浏览(46)
  • 算法训练day31贪心算法理论基础Leetcode455分发饼干376摆动序列53最大子序和

    文章链接 代码随想录 (programmercarl.com) 说实话贪心算法并没有固定的套路 。 最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧 。 面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了 。 刷题或者面

    2024年02月20日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包