目录

先根遍历：根左右

中根遍历：左根右

后根遍历：左右根

下面做俩题就懂了

​

先根遍历：根左右

中根遍历：左根右

后根遍历：左右根

下面做俩题就懂了

题一： 

先根遍历:ABCDEFGH
中根遍历:CBEDFAGH
后根遍历:CEFDBHGA

题二： 

前根序列:-+A*BC/DE
中根序列:A+B*C-D/E
后根序列:ABC*+ DE/-

题三：

前根序列: ABDEGCFH
中根序列: DBGEACHF
后根序列: DGEBHFCA

1.递归建立二叉树

  由中根遍历的数组和后根遍历的数组建立一棵二叉树，其中参数inOrder是整棵树的中根遍历，postOrder是整棵树的后根遍历，inIndex是 中根遍历从inOrder字符串中的inOrder的最后一个位置，postIndex是后根遍历从字符串postOrder 中的最后一个位置，count表示树结点的个数。

public BiTree( String postOrder, String inOrder, int postIndex,int inIndex,int count) {

 if (count > 0) {// 中根和后根非空

char r = postOrder.charAt(postIndex);// 取后根字符串中的最后一个元素作为根结点
int i =0 ;
for (; i<count; i++) {
 
 // 寻找根结点在中根遍历字符串中的索引
 if (r == inOrder.charAt( inIndex-i)) {
  break;
 }
 }
root = new BiTreeNode(r);// 建立树的根结点
root.rchild= new BiTree( postOrder,inOrder,postIndex-1,inIndex, i).root;// 建立树的右子树
root.lchild= new BiTree( postOrder, inOrder,postIndex-i-1,inIndex -i-1,count-i-1).root;// 建立树的左子树


}
}

2.实现类

public class test {

 public static void main(String[] args) {

String postOrder = "DGEBHFCA";

String inOrder = "DBGEAFHC";

BiTree T = new BiTree(postOrder,inOrder,postOrder.length()-1,postOrder.length()-1,postOrder.length());

System.out.println("先根遍历为:");

BiTreeNode root = T.getRoot();      //取得树的根结点

T.preRootTraverse(root);

System.out.println();

 System.out.println("后根遍历");

T.postRootTraverse(root);

System.out.println();

System.out.println("中根遍历");

T.inRootTraverse(root);

 }
}

3.运行结果：

先根遍历为:
ABDEGCFH
后根遍历
DGEBHFCA
中根遍历
DBGEAFHC

题一：

已知一棵树二叉树的 后根遍历 和 中根遍历 的序列分别为: ACDBGIHFE 和 ABCDEFGHI，

请画出该二叉树,并写出它的先根遍历的序列

答：

先根遍历序列：EBADCFHGI

解题思路：

我们先找到根

  后根：左  右  根                                         中跟：左  根  右 

 ACDB    GIHF   E                                           ABCD   E    FGHI

我们先从后根去找，这个根一定是在这个遍历的后面，我们就可以确定E是根

然后我们在中根遍历中找到E的位置，所以E的左边就是左指数节点，右边是右指数节点

现在最上面的数E确定了，那谁是E左指数上的根呢，谁在后面谁是根：是B

然后再看中根遍历，谁在B的左边谁是左指数：是A；于是:

现在在左指数上只有C和D没有画出来，

看中根遍历得到：C和D在B的右边，看后根遍历知道D在后面，所以D是根，

在中根遍历中，C在D的左边，所以C是D的左指数；

于是：以E为根节点的左指数画完

接下来看看以E为根节点的右指数，先在后根遍历中找根节点，谁在后面谁是根节点：是F

再到中根遍历中找到F位置，F左边画完了，所以没有左指数，再看右边：GHI

回到后根遍历看GHI，得知H是根节点，所以：

现在只剩G、I 没有画了，所以回到中根遍历中看到G在H左，I 在H右，所以：

如果想知道画的对不对，带进题干，看看他的后根遍历和中根遍历对不对就行了

题二：

已知一棵树二叉树的先根遍历和中根遍历的序列分别为:ABDGHCEFI和GDHBAECIF，

请画出此二叉树，并写出它的后根遍的序列

构造的二叉树如下

后根遍历序列: GHDBEIFCA

解题思路：
首先先找根

先根： 根   左   右                              中根： 左  根  右 

        A    BDGH    CEFI                          GDHB   A   ECIF

看先根遍历得知A是根，然后在中根遍历中找到A的位置

所以得知GDHB在A的左边，ECIF在A的右边

那GDHB是谁根呢？回到先根遍历中，谁在前面谁是根，得知是B

再看中根，GDH在B的左边，那就是B的左指数

那GDH种谁是根呢？看先根中，D在前，那D就是根

再去中根遍历中找D的位置，得知左是G，右是H

现在以A为根节点的左指数已全部找到，那右指数就是ECIF

回到先根遍历中，那这四个谁在前面谁是根，是C

再去中根遍历中找C的位置，E在C的左边（左指数），I F在C的右边（右指数）

那 I F谁是根呢？去先根遍历中找：F在前，F是根

中根遍历中 I 在 F 左，于是 I 是F的左指数