问答题 一棵2-3树的形状定义如下:
·一个结点包含一个关键字或两个关键字。
·每个结点最少有两个子女(如果它包含一个关键字),最多有三个子女(如果它包含两个关键字)。
·每个结点的结构是(leftChild,leftKey,midChild,rightKey,rightChild)。
其中,关键字leftKey<rightKey,且指针leftChild所指子树上所有结点包含的关键字均小于leftKey;指针midChild所指子树上所有结点包含的关键字均大于leftKey,小于rightKey;指针:rightChild所指子树上所有结点包含的关键字均大于rightKey。
·所有失败结点都在树的同一层上,它们都是查找失败到达的结点,指向它们的指针都是空的。因此树的高度总是平衡的。
根据以上定义,试回答下列问题,并说明理由:
问答题 2-3树可否看作是B树的特殊情况?
【正确答案】
【答案解析】2-3树可以看作是3阶B树,它们在形态上都是一样的,都是有序树。但2-3树定义中有左、中、右子树之分,B树是第0棵、第1棵、第2棵子树。
问答题 2-3树可否看作是平衡的3叉查找树?
【正确答案】
【答案解析】2-3树可以看作是平衡3叉查找树。正像B树可以继承m路查找树一样,2-3树可以继承3叉查找树,但平衡性要求更高。
问答题 平衡的3叉查找树可否看作是2-3树?
【正确答案】
【答案解析】平衡的3路查找树不一定是2-3树。因为平衡的3叉查找树的叶结点不要求一定在同一层上,而2-3树有此要求。
问答题 二叉排序树可否看作是二叉树的特殊情况?
【正确答案】
【答案解析】二叉排序树是二叉树的特殊情况,二叉排序树继承了二叉树,但它限制结点中的数据必须满足:根的左子树中所有结点的关键字值必须小于根结点的关键字值,根的右子树中所有结点的关键字值必须大于根结点的关键字值。