结构基础考试真题

(1)确定根节点:从后续来看，Un是根节点；如果在中间序列中找到Un，则可以知道左子树在Un之前，右子树在Un之后。

(2)分割:用Un分割中间序列up1，up2，...upn分为左子树中的中间序列，Un和右子树中的中间序列；使用获得的左子树序列和右子树序列，后序序列U1，U2...Un分为左子树序列、UN和右子树序列。

(3)递归划分新的根节点:用(1)(2)的方法将左子树(左子树的中间序列，左子树的后续序列)和右子树(右子树的中间序列，右子树的后续序列)得到的根节点划分为Un的左右子节点，直到任意一个子树的节点被划分。

- E

-丙

- K

- D

- J

A

我

- G

- H

-乙

- F

打印订单:A B F G H I C D J K E

按顺序打印:F B H G I A J D K C E

I G B J K D E C A

从上面的证明过程可以看出:

(1)知道了优先顺序和中间顺序也可以确定一棵树的结构。

(2)知道先行序列和后继序列并不能确定一棵树的结构，因为只能确定根，而不能确定左右子树。这里有一个反例:

A

-乙

- F

打印_预购_订单:A B F

打印_过帐_订单:F B A

按顺序打印

- F

-乙

A

打印_预购_订单:A B F

打印_过帐_订单:F B A

按顺序打印

在这个例子中，两棵树有不同的结构，但是它们的前序和后续序列是相同的。