有关键码值为15,25,40的三个结点。按所有可能的插入顺序去构造二叉排序树,能构造出___________棵

Question

有关键码值为15，25，40的三个结点。按所有可能的插入顺序去构造二叉排序树，能构造出___________棵不同的二叉排序树。

Answer 1

正确答案：
5或五【解析】二叉排序树是将线性表中的结点信息(或结点中的关键码值和结点地址)组织成二叉树形式，以达到与二分法检索相同的检索效率，而又具有链表那样的插入、删除、运算的灵活性。二叉树的特点：每个结点的左子树中所有的结点的关键码值都小于该结点的关键码值，而右予树中所有结点的关键码值都大于该结点的关键码值。对于插入排序所形成的二叉树的总数目为：C(2n，n)/(n＋1)＝C(6，3)/4＝5，其中n1为关键码的个数。