Question

如何根据后序遍历和中序遍历建立二叉树

Answer 1

这里的“先根”也叫做先序，“中”和“后”也一样。
先序遍历是先访问当前节点，然后再遍历左子树，最后是右子树。
中序遍历是先遍历左子树，再访问当前节点，最后是右子树。
后序遍历是先遍历左子树，再遍历右子树，最后访问当前节点。
例：
一棵二叉树的先根遍历为abcdefg，中根遍历为cbdeagf，则其后根遍历为
：
1、先序遍历的第一个当前节点一定是根节点，所以a是根
2、由于中序遍历是先遍历完左子树再访问当前节点，所以可以看出中序序列在a之前的都是a的左子树中的节点，而在a之后是a的右子树的节点。
3、这样就分成了（cbde）a
(gf),三个集合。
4、我们分别再看各个集合。cbde集合中最先在先序序列中出现的是b，这说明b在这个集合中应该是第一个出现的。所以右可以再分
********a
**b********(gf)
c**(de)
5、再看de，在先序序列中因为d在e前方，所以d肯定是e的父节点，现在剩下的就是判断e是d的左孩子还是右孩子。从中序序列中看，d仍然是在e的前方，说明e是d的右孩子。
********a
**b********(gf)
c***d
******e
6、最后剩下gf.和de相似的判断方法，在先序序列中f在g前方，说明f是父节点，而在中序当中g在f前方，说明g是f的左孩子。
所以这颗二叉树应该是
********a
**b********f
c***d*****g
******e
7、二叉树出来了，后序的原理最上方讲了，剩下的就好办了。先左孩子，然后右孩子，最后当前节点。
8、当前节点为a时由于左右两个子树还没有访问所以要先访问完左右子树才能访问a.
9、b同a
10、c没有左右孩子，所以它是第一个。
11、c访问完了在访问b的右子树。
12、先访问d的孩子e,然后再是d。
13、b的左右孩子都访问完了，所以下一个是b。
14、访问完b，a的左子树访问完了，但是还是不能访问a，因为a的右子树还没有访问。
15、a的右子树中，g是f的孩子，所以先g再f。
16、最后是根节点a。

Answer 2

前序遍历:1
2
4
8
9
10
11
5
3
6
7
(规律：根在前；子树在根后且左子树比右子树靠前)；
中序遍历:8
4
10
9
11
2
5
1
6
3
7
(规律：根在中；左子树在跟左边，右子树在根右边)；
后序遍历:8
10
11
9
4
5
2
6
7
3
1
(规律：根在后；子树在根前且左子树比右子树靠前)；
其它例子：
前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
前序遍历:1
2
4
3
5
7
6
中序遍历:2
4
1
5
7
3
6
后序遍历:4
2
7
5
6
3
1
做类似的题目，你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历，写的方法如上（递归）。画出二叉树的方法如下：
已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：
1.
根据前序序列的第一个元素建立根结点；
2.
在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3.
在前序序列中确定左右子树的前序序列；
4.
由左子树的前序序列和中序序列建立左子树；
5.
由右子树的前序序列和中序序列建立右子树。
已知一棵二叉树的后序序列和中序序列，构造该二叉树的过程如下：
1.
根据后序序列的最后一个元素建立根结点；
2.
在中序序列中找到该元素，确定根结点的左右子树的中序序列；
3.
在后序序列中确定左右子树的后序序列；
4.
由左子树的后序序列和中序序列建立左子树；
5.
由右子树的后序序列和中序序列建立右子树。
另外,站长团上有产品团购,便宜有保证