第7章集合与搜索 ○○○○@①③○○ (3)按i和j为根的树的结点个数实现 union(,j),结点个数大者为结点个数小者的双亲 (⑩①①众 ③⑦③8@ 7-16有n个结点的二叉搜索树具有多少种不同形态? 【解答】 7-17设有一个标识符序列{else, public, return, template},p1=0.05,p2=0.2,p=0.1,p=005,90=0.2,q=0.1 q=0.2,q3=0.05,q4=0.05,计算Wl、CIU和RU,构造最优二叉搜索树。 【解答】 将标识符序列简化为{e,p,r,t},并将各个搜索概率值化整,有 P (1)首先构造只有一个内结点的最优二叉搜索树 三个矩阵的内容如下 07 01234 (2)构造具有两个内结点的最优二叉搜索树第 7 章 集合与搜索 62 (3) 按 i 和 j 为根的树的结点个数实现 union(i, j)，结点个数大者为结点个数小者的双亲。 7-16 有 n 个结点的二叉搜索树具有多少种不同形态? 【解答】 7-17 设有一个标识符序列{else, public, return, template}，p1=0.05, p2=0.2, p3=0.1, p4=0.05, q0=0.2, q1=0.1, q2=0.2, q3=0.05, q4=0.05，计算 W[i][j]、C[i][j]和 R[i][j]，构造最优二叉搜索树。 【解答】 将标识符序列简化为 { e, p, r, t }，并将各个搜索概率值化整，有 e p r t p1 = 1 p2 = 4 p3 = 2 p4 = 1 q0 = 4 q1 = 2 q2 = 4 q3 = 1 q4 = 1 (1) 首先构造只有一个内结点的最优二叉搜索树: 三个矩阵的内容如下: 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 4 7 0 0 7 0 0 1 1 2 10 1 0 10 1 0 2 2 4 7 2 0 7 2 0 3 3 1 3 3 0 3 3 0 4 4 1 4 0 4 0 W[i][j] C[i][j] R[i][j] (2) 构造具有两个内结点的最优二叉搜索树 C n n n 2 1 1 + 0 11 12 13 4 5 6 10 11 12 13 3 1 2 7 8 9 15 16 0 14 p1 p2 p3 p4 q0 q1 q1 q2 q2 q3 q3 q4