设有二叉排序树如题29图所示。请回答下列问题。 
（1）假定二叉排序树初始为空，写出一个数据输入序列，按序插入时能得到题29图所示的二叉排序树。 （2）能得到题29图所示的二叉排序树的不同的输入数据序列有几个？
【正确答案】：（1）a g e b f d c；（2）4个
【题目解析】：从上到下遍历，有左右子树，则会有本同的序列。本题：遍历可以得到agebfdc。以e为根的树有左右子树，其左右子树之间序列位置可以调换。遍历能得到题29图所示的二叉排序树的不同的输入数据序列 agebfdc；agebdfc；agebdcf；agefbdc；共四个。
