|
先序、中序以及后序遍历是我们遍历二叉树常用方法，当然还有层级遍历。前三者属于深度优先遍历，后者属于广度优先遍历。今天我们谈谈前面三种遍历的关系。即，已知先序、中序、后序遍历中的哪几种可以确定一棵树的结构，从而得出另一种或两种遍历的结果。 首先假设我们只知道三种遍历中的一种的结果。显然只知道一种遍历结果不能确定一棵树的结构，先序遍历和后序遍历只能找到根节点，不能判断左右子树；中序遍历甚至连根节点都找不到。 那么假设我们知道三种遍历中的两种呢？假如我们知道了先序遍历和中序遍历的结果（树中所有节点元素的值两两都不相同），要求后序遍历的结果。做法是先找到先序遍历的第一个元素，它肯定是这棵树的根节点元素的值；然后到中序遍历结果中找这个值，那么中序遍历中这个值前面的所有元素都是根节点的左子树的节点的值，后面的所有元素都是根节点你的右子树的节点的值。现在我们对左右子树分别进行相同的操作，即递归调用当前的这个函数，就能构造出一棵完整的二叉树。 同理的，假如我们已经知道了后序遍历和中序遍历的结果，一样能够用相同的方法还原这棵二叉树。 但是，如果知道了先序遍历和后序遍历的结果，能不能还原这可二叉树呢？答案是不能。因为先序遍历和后序遍历本质上是一样的，先序遍历是先访问根节点再遍历左右子树，后序遍历是先遍历左右子树再访问根节点，因此我们即使知道了根节点也不能区分出左右子树。但是如果是中序遍历，我们知道了它的根节点就能知道它的左右子树，所以中序遍历在还原二叉树过程中是最重要的。不过仅仅知道中序遍历我们并不能知道哪个是它的根节点元素的值，所以还得通过先序遍历或者后序遍历来找到根节点。 下面是我写的通过先序遍历和中序遍历结果还原二叉树的程序>_ |