树的后序遍历序列等同于该树对应的二叉树的______。A.先序序列B.中序序列C.后序序列D.不确定

Question

树的后序遍历序列等同于该树对应的二叉树的______。

A．先序序列

B．中序序列

C．后序序列

D．不确定

Answer 1

正确答案：B
解析：树的后序遍历是指先依次后序遍历每棵子树，然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时，可以找到唯一的一棵二叉树与之对应，我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知，树的后序遍历序列等同于该树对应的二叉树的中序遍历。例如，图3-80展示了一个转化实例。由图3-80可以看出，树的后序遍历和其对应的二叉树的中序遍历都是BDCEA。注意，对于树而言，没有中序遍历。