c++二叉树_大牛带你学|由二叉树的遍历序列求二叉树结构的解题方法归纳

前言

二叉树章节 属于数据结构考察的三大重点章节(线性表、树、图)之一&＃xff0c;不管是在自命题院校考察和408统考都是考察频次很高的考点。今天&＃xff0c;大牛学长就来为各位同学总结归纳一个二叉树知识考察中的常见题型的解题方法。

在二叉树相关考察中&＃xff0c;有这样一类题型&＃xff0c;它形如【已知二叉树的中序遍历序列和先序遍历序列&＃xff0c;求二叉树的后序遍历序列】同时&＃xff0c;这类题很容易在选择题中衍生成其他题型&＃xff0c;因此掌握它的固定解法是相当重要的。由于在解得二叉树的形态后求相关遍历序列非常简单&＃xff0c;我们把这一类问题归结为&＃xff1a;【由二叉树的遍历序列求二叉树结构】。

要解决这一类问题&＃xff0c;我们需要先回顾一下二叉树的结构以及它的四种遍历方式的特点。我们知道任何二叉树可以分为三部分&＃xff1a;根结点(D)、左子树(L)、右子树(R)。所谓遍历二叉树&＃xff0c;就是按某种顺序访问这三个部分。根据不同顺序可以把遍历方法分层三类&＃xff1a;

DLR——先(根)序遍历。

LDR——中(根)序遍历。

LRD——后(根)序遍历。

同时我们也可以按层次观察&＃xff1a;

从根结点开始遍历&＃xff0c;按层次次序&＃xff0c; “自上而下&＃xff0c;从左至右”访问树中的各结点。

先序遍历ABDEC

中序遍历DBEAC

后序遍历DEBCA

层序遍历ABCDE

由此我们得到了四种遍历方式&＃xff1a;先序遍历、中序遍历、后序遍历、层序遍历。

根据大牛学长画出的示意图&＃xff0c;我们一起观察一下四种遍历方式的特点&＃xff1a;

对于根结点A来说&＃xff0c;左子树对应的是BDE这三个结点&＃xff0c;右子树对应的是C这个结点。

• 先序遍历&＃xff1a;DLR&＃xff0c;以A为根结点的先序遍历序列是ABDEC&＃xff0c;以B为根结点的先序遍历序列是BDE&＃xff0c;以C为根结点的先序遍历序列是C。显然在先序遍历的序列当中&＃xff0c;我们可以根据DLR划分为三个部分 (A)(BDE)(C)&＃xff0c;并且每一个部分都符合先序遍历。

• 后序遍历&＃xff1a;LRD&＃xff0c;以A为根结点的后序遍历序列是DEBCA&＃xff0c;以B为根结点的后序遍历序列是DEB&＃xff0c;以C为根结点的后序遍历序列是C。显然在后序遍历的序列当中&＃xff0c;我们可以根据LRD划分为三个部分 (DEB)(C)(A)&＃xff0c;并且每一个部分都符合后序遍历。

• 中序遍历&＃xff1a;LDR&＃xff0c;以A为根结点的中序遍历序列是DBEAC&＃xff0c;以B为根结点的中序遍历序列是DBE&＃xff0c;以C为根结点的中序遍历序列是C。显然在中序遍历的序列当中&＃xff0c;我们可以根据DLR划分为三个部分(DBE)(A)(C)&＃xff0c;并且每一个部分都符合中序遍历。

• 层序遍历&＃xff1a;以A为根结点的中序遍历序列是ABCDE&＃xff0c;以B为根结点的中序遍历序列是BDE&＃xff0c;以C为根结点的中序遍历序列是C。层序遍历的分析比较复杂&＃xff0c;但是我们可以根据已知的树结点的情况对遍历序列进行划分&＃xff0c;划分为(A)(BCDE)两部分。显然层序遍历的第二部分当中左子树和右子树的结点是交替输出的&＃xff0c;不像前三种遍历左子树和右子树独立输出&＃xff0c;但是我们可以根据已知左子树对应的是BDE这三个结点&＃xff0c;在遍历序列ABCDE当中选取BDE三个结点保留他们的相对位置&＃xff0c;得到的(BDE)对应的正是左子树的层次遍历&＃xff0c;同样的根据右子树对应的是C这个结点&＃xff0c;在遍历序列中选取的(C)对应的正是右子树的层次遍历。

对于先序遍历、后序遍历以及层序遍历来说&＃xff0c;都能够唯一地确定根结点的值&＃xff01;这一点异常重要&＃xff01;

先序遍历和层序遍历中根结点总是在序列的 第一位&＃xff0c;

后序遍历中根结点总是在序列的 最后一位。

对于中序遍历来说&＃xff0c;如果能够唯一地确定根结点的值&＃xff0c;设根结点所在下标为i&＃xff0c;那么[0...i-1]对应的就是左子树的中序遍历序列&＃xff0c;[i&＃43;1...n]对应的就是右子树的中序遍历序列。

由此我们可以确定左子树拥有哪些结点&＃xff0c;以及右子树拥有哪些结点。

要知道&＃xff0c;通过遍历序列确定二叉树形态这样的操作虽然很常见&＃xff0c;但是&＃xff0c;存在不能确定形态的情况&＃xff01;

(一)单一的遍历序列不能够确定唯一一个二叉树

(二)四种遍历序列中&＃xff0c;任意取其两种&＃xff0c;也不一定能够确定二叉树具体确定情况如下表所示。可以看出&＃xff0c;确定二叉树的规则可以总结为&＃xff1a;

中序遍历是必须&＃xff01;其余三种取其一。

任何不满足这个口诀的序列方法都是不能唯一确定二叉树的&＃xff01;

对于为什么不能通过先序遍历、后序遍历、层序遍历三者中的任意组合唯一确定二叉树&＃xff0c;可以参考上面的分析过程&＃xff0c;也可以记住一个这样的反例。这两个不相同的二叉树拥有相同的先序遍历、后序遍历、层序遍历序列。

前面提到了通过先序遍历、后序遍历以及层序遍历能够唯一地确定根结点的值。当我们通过以上的三种序列之一拿到根节点值之后&＃xff0c;观察中序遍历序列可以确定左子树和右子树拥有的结点情况。

若能确定先序遍历、后序遍历哪些结点属于左子树或右子树&＃xff0c;对应的左子树和右子树的先序遍历、后序遍历又能唯一地确定其根结点的值。

这时候&＃xff0c;将子树当成一棵新的树&＃xff0c;重新去重复“找根节点、划分左右子树”的流程&＃xff0c;直到找到所有叶子节点&＃xff0c;二叉树的形态确定过程基本也就完成了。

在整理好逻辑之后&＃xff0c;大牛学长来跟大家归纳常考的题型。

具体试卷上&＃xff0c;一般考察知道中序遍历序列&＃xff0c;以及先后序遍历序列之一的二叉树确定问题(结点数量为n&＃xff0c;序列下标从0开始)。根据前面的逻辑整理&＃xff0c;这种情况的解题步骤可以归纳为&＃xff1a;

(1)在先序遍历(后序遍历)中选择 第一个(最后一个)作为根结点T

(2)在中序遍历中寻找T&＃xff0c;确定下标为i&＃xff0c;则左子树为inorder[0...i-1]长度为i&＃xff0c;右子树为inorder[i&＃43;1...n-1]长度为n-i-1

(3)在先序遍历(后序遍历)中以preorder[1...i](postorder[0...i-1])为左子树&＃xff0c;对左子树执行(1)&＃xff0c;以preorder[i&＃43;1...n-1](postorder[i...n-2])为右子树&＃xff0c;对右子树执行(1)

而对于已知层序遍历和中序遍历(结点数量为n&＃xff0c;序列下标从0开始

)唯一确定二叉树基本的解题步骤为&＃xff1a;

(1)在层序遍历中选择 第一个(最后一个)作为根结点T

(2)在中序遍历中寻找T&＃xff0c;确定下标为i&＃xff0c;则左子树为inorder[0...i-1]长度为i&＃xff0c;右子树为inorder[i&＃43;1...n-1]长度为n-i-1

(3)在层序遍历中按照inorder[0...i-1]遍历整个levelorder序列确定i个结点为左子树&＃xff0c;对左子树执行(1)&＃xff0c;按照inorder[i&＃43;1...n-1]确定n-i-1个结点为右子树&＃xff0c;对右子树执行(1)

题目&＃xff1a;若某一二叉树的先序遍历序列为ABDEC&＃xff0c;其中序遍历序列为DBEAC&＃xff0c;求该二叉树的形态(恢复该二叉树)。

解答&＃xff1a;

(1) 由于知道了该二叉树的先序遍历序列&＃xff0c;可知其根节点为A。

(2) 将A拿到中序遍历序列中&＃xff0c;可以看到A把二叉树分成了两部分&＃xff0c;左子树DBE&＃xff0c;右子树C。

(3) 对于整个二叉树来说&＃xff0c;根节点A和A的唯一右子树(一个节点)C已经确定&＃xff0c;接下来需要确定其右子树DBE(中序序列)了。

(4) A的左子树的先序遍历序列是BDE&＃xff0c;因此很明确的知道B是左子树的根节点&＃xff0c;也就是A的左儿子&＃xff0c;于是把B节点拿到中序序列DBE中&＃xff0c;看出B刚好把D、E分开&＃xff0c;于是可以得到左子树是以B为根节点&＃xff0c;D、E分别为左右子树的二叉树&＃xff0c;将该二叉树放到A的左子树位置即可。最终树的形态如下图所示。

好啦&＃xff0c;对于如何从两种二叉树遍历序列中求出二叉树形态类型题的总结和归纳就到此为止啦&＃xff01;希望同学们能够从中得到提升哟~

大牛学长也会不断发掘考点考题&＃xff0c;为大家带来更加丰富有用的知识、题型总结&＃xff01;

今天是2020年8月14日

距离2021年考研还有 126 天  

乾坤未定&＃xff0c;你我皆是黑马。

大牛学长一直在~