知道二叉树两种遍历求第三种遍历该用什么方法？

RT

yyy6030119944 · 2018-4-30 01:57:03

序中序和后序都是指的是遍历父节点的顺序，例如前序遍历，指的就是先遍历父节点，然后是左子女，然后右子女；那么中序遍历的话就是，先左子女，然后父节点，然后右子女；后序就是先左子女，然后右子女，然后父节点

你只要记住这个序指的什么就好了，二叉树遍历这三种顺序都是先左子女后右子女的

溪畔y · 2018-4-30 01:57:04

由两种遍历所得的顺序能唯一确定一棵二叉树，
比如给定了一颗二叉树的先序序列是:ABDECFG,中序序列是：DBEAFCG，

聽由先序序列可以确定该二叉树根为A,因为先序遍历的顺序是从根到左子树再到右子树，然后从中序序列中，可以得知DBE在A的左子树，而FCG在A的右子树，
聽由于在先序序列中B紧跟在A后，所以B肯定是A左子树的树根，再看中序序列里，A的左子树是DBE，由中序序列遍历的顺序为：左子树，双亲，右子树，可知D为B的左子树，E为B的右子树，
同样可以分析树根A的右子树，先序序列中ABDE已经将树根和左子树遍历完成，所以剩下的CFG是右子树的先序遍历序列，可知C为右子树的树根，F为C的左子树，G为C的右子树，所以
该二叉树按层序遍历的顺序应该是ABCDEFG。

爱你oneyear · 2018-4-30 01:57:05

知道两种遍历（只能是先序遍历和前序遍历）、（中序遍历和后序遍历））然后画出图，接着不就知道第三种遍历了吗？
~~~~~~~~~~~~~~~~~~~~~~~~~~~ 就是这个方法~~~~~~~~~~~~~~~~~~~

8269680 · 2018-4-30 01:57:06

首先，应掌握其方法，先序：中左右；中序：左中右；后序，左右中；
假设该二叉树的先序为：1245637；中序为：4265173；
看先序，第一位为1，1就为二叉树的第一位。在看中序，可得该二叉树左边为：2，4；右边为：5，7，3，6；将中序分为两部分：2，4与3，5，7，6，这样1的两个子结点为2和3。看中序，4在2前面，4就在2的左边，5和7在3的前面，那么5和7就在3的左边，6在3的右边。最后要确定5和7的位置，看先序，5在7的前面，因此5在3的左边，7在5的左边。由此得树：

如图：       1
         /  \
         2    3
      /    /  \
      4    5 6
            /
         7
后序为：4652731
用此方法，若已知其两种遍历，画出该图，就可求得第三种遍历

0hz0 · 2018-4-30 01:57:07

用递归画出二叉树再求解

知道二叉树两种遍历 求第三种遍历 该用什么方法？

5 个回复

知道二叉树两种遍历求第三种遍历该用什么方法？