次优二叉树
原理 首先取出查找表中每个关键字及其对应的权值，采用如下公式计算出每个关键字对应的一个值：
其中 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.……