数据结构第7章(4)

} }

7-30 回答下列问题： (1) 直接在二叉搜索树中搜索关键码为key的对象与从中序遍历输出的有序序列中顺序搜索关键码为key的对象，其效率是否相同？

(2) 输入关键码有序序列来构造一棵二叉搜索树，然后对此树进行搜索，试分析其效率。 【解答】 (1) 效率不相同。在二叉搜索树中平均搜索效率高于有序表的顺序搜索。 (2) 其效率等同于有序表的顺序搜索。因为按关键码有序序列构造出来的二叉搜索树是一棵向右倾斜的单支树，失去了二叉搜索树的优点。

7-31 设在一棵二叉搜索树的每个结点中，含有关键码key域和统计相同关键码结点个数的count域，当向该树插入一个元素时，若树中已存在与该元素的关键码相同的结点，则就使该结点的count域增1，否则就由该元素生成一个新结点而插入到树中，并使其count域置为1，试按照这种插入要求编写一个算法。 【解答】

template

void BST :: Insert1 ( const Type& value ) {

//向二叉搜索树中插入一个元素value, 若树中存在该元素, 则将匹配结点中的count域 //的值加1即可

BstNode *p = root, *pr = NULL;

while ( p != NULL ) {

pr = p;

if ( value == p->data ) break;

}

if ( p != NULL ) p->count++; else {

//若元素已存在，将其count域的值增1 //否则建立新结点并插入到合适位置

else if ( value < p->data ) p = p->leftChild;

else p = p->rightChild;

//p是检测指针, pr是其双亲指针 //在树中搜索关键码为value的结点

BstNode *s = new BTreeNode; s->data = value; s->count = 1; s->leftChild = s->rightChild = NULL; if ( pr == NULL ) root = s; else pr->rightChild = s; } }

//空树情形

//非空树情形, 接在双亲下面

else if ( value < pr->data ) pr->leftChild = s;

7-32 设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }, (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。

(2) 计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】

(1) 构造平衡二叉搜索树的过程

151

31 55 31 右旋 左右旋 左旋 31 11 55 11 55 11 37 37 46 46 73 46 46 46 31 55 右左旋 31 63 左右旋 31 63 11 11 37 73 37 55 73 07 37 55 73 63 02 02 11 07 (2) 计算在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。

ASLsucc = (1/9)*(1+2*2+3*4+4*2)=25/9 ASLunsucc = (1/10)*(3*6+4*4)=17/5

152