原理

首先取出查找表中每个关键字及其对应的权值，采用如下公式计算出每个关键字对应的一个值：

file

其中 wj 表示每个关键字的权值（被查找到的概率），h 表示关键字的个数。

表中有多少关键字，就会有多少个 △Pi ，取其中最小的做为次优查找树的根结点，然后将表中关键字从第 i 个关键字的位置分成两部分，分别作为该根结点的左子树和右子树。同理，左子树和右子树也这么处理，直到最后构成次优查找树完成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71


typedef int KeyType;//定义关键字类型

typedef struct{

    KeyType key;

}ElemType;//定义元素类型

typedef struct BiTNode{

    ElemType data;

    struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;



//定义变量

int i;

int min;

int dw;

//创建次优查找树，R数组为查找表，sw数组为存储的各关键字的概率（权值），low和high表示的sw数组中的权值的范围

void SecondOptimal(BiTree T, ElemType R[], float sw[], int low, int high){

    //由有序表R[low...high]及其累计权值表sw（其中sw[0]==0）递归构造次优查找树

    i = low;

    min = abs(sw[high] - sw[low]);

    dw = sw[high] + sw[low - 1];

    //选择最小的△Pi值

    for (int j = low+1; j <=high; j++){

        if (abs(dw-sw[j]-sw[j-1])<min){

            i = j;

            min = abs(dw - sw[j] - sw[j - 1]);

        }

    }

   

    T = (BiTree)malloc(sizeof(BiTNode));

    T->data = R[i];//生成结点（第一次生成根）

    if (i == low) T->lchild = NULL;//左子树空

    else SecondOptimal(T->lchild, R, sw, low, i - 1);//构造左子树

    if (i == high) T->rchild = NULL;//右子树空

    else SecondOptimal(T->rchild, R, sw, i + 1, high);//构造右子树

   

}

完整事例演示

例如，一含有 9 个关键字的查找表及其相应权值如下表所示：

file

则构建次优查找树的过程如下：首先求出查找表中所有的 △P 的值，找出整棵查找表的根结点：

例如，关键字 F 的 △P 的计算方式为：从 G 到 I 的权值和 - 从 A 到 E 的权值和 = 4+3+5-1-1-2-5-3 = 0。 

通过上图左侧表格得知，根结点为 F，以 F 为分界线，左侧子表为 F 结点的左子树，右侧子表为 F 结点的右子树（如上图右侧所示），继续查找左右子树的根结点： file

通过重新分别计算左右两查找子表的 △P 的值，得知左子树的根结点为 D，右子树的根结点为 H （如上图右侧所示），以两结点为分界线，继续判断两根结点的左右子树： file

通过计算，构建的次优查找树如上图右侧二叉树所示。后边还有一步，判断关键字 A 和 C 在树中的位置，最后一步两个关键字的权值为 0 ，分别作为结点 B 的左孩子和右孩子，这里不再用图表示。

注意：在建立次优查找树的过程中，由于只根据的各关键字的 P 的值进行构建，没有考虑单个关键字的相应权值的大小，有时会出现根结点的权值比孩子结点的权值还小，此时就需要适当调整两者的位置。