如果题目给你画出了一颗二叉树,要求找出生成该二叉排序树的关键字的初始排列有几种?
请问如何确定全部排列?请给出解题思路,我的图怎么传不上来,只好用文字说明该题了。严老师习题集9.10题!请高手指教,谢谢!
[解决办法]
5
/ \
4 7
/ /
2 6
/ \
1 3
第一个来的一定是根节点5,这个毫无悬念,后面就要费一番周折了:
先看右子树,顺序一定是76,只有这一种情况;
再看左子树,可能是4213,也可能是4231,有两种可能。
最后将左右子树的情况组合起来(比如说,右子树的两个节点7和6,可以在4213这个左子树序列中挑两个不同的空挡分别插入,也可以挑同一个空挡一起插入……),这样总共下来就是2*C(6,2)=30种。