已知一棵二叉树的中序序列和后序序列分别为c,b,a,e,d,h,g,j,i,f 和 c,b,e,h,j,i,g,f,d,

1个回答

  • 这个问题我答了几次,搜一下就有答案了:

    很简单.这也是个递归过程.

    知道后序,就能找到“根”,是最后一个节点.

    知道“根”节点,就好办了,从中序中把根结点找到,它左边是左子树的中序,

    右边是右子树的中序,知道这两子树的中序,就能从后序中,把左子序、右子树

    找出来(据中序的左、右子树的结点数).

    这样,根节点找出来了,左子数的后序、中序就分离出来了,右子数也分离出来了,

    这个问题,就化成两个新树的问题.同样的办法如此,就是递归成两个子树的新问题.

    如果用程序,一样用递归就做出来了.

    如:后序中最后一个a就是根,从中序就能分出左右子树:

    c b及 e d h g j i f 这是中序;

    就可从后序分出左右子树:

    cb 及 e h j i g f d

    这个问题就变成了两个树的同样问题了.

    左子树的中序c b,后序 c b

    右子树的中序e d h g j i f 后序 e h j i g f d

    就可推算出一颗整树 .

    你就可用递归的办法写出程序.