问答题
已知一棵树的先根次序遍历的结构与其对应二叉树表示(子女-兄弟链表表示)的前序遍历结果相同,树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。请回答以下问题:
问答题
利用树的先根遍历结果和后根遍历结果能否唯一确定一棵树?举例说明。
【正确答案】
【答案解析】因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树,因此,根据题目给出的条件,利用树的先根次序遍历结果和后根次序遍历结果能够唯一地确定一棵树。例如,对于下图中左图所示的树,对应二叉树的前序序列为1,2,3,4,5,6,8,7,中序序列为3,4,8,6,7,5,2,1。原树的先根遍历序列为1,2,3,4,5,6,8,7,后根遍历序列为3,4,8,6,7,5,2,1。

问答题
n个结点的不同形状的树有多少种?
【正确答案】
【答案解析】确定n个结点的不同树的数目可以归结到确定其对应二叉树的计数。因为树转化为二叉树后,根结点没有右子女,该二叉树的计数归结到对应二叉树根下左子树可能有多少种不同构造。可以利用n-1个结点的catalan函数来计算。