查找顺序表时，，若 每个元素的概率 都相等 用 二分查找 效率 最高。但是 如果 概率 不相等时，（SOST）静态最优查找表 效率 要高于 二分查找。静态最优查找表 是 使得 从 根 到 每个节点的路径 长度 和 权值 乘积 之和 最小。
书上说的 静态最优 查找树的创建 时间 复杂度 较高，所以 用 次优 查找树(NOST) 代替。
下面 上代码：
// Nost.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <cstdlib>#include <cmath>typedef struct Node{//次优查找树.char data;Node * leftChild;Node * rightChild;}*NosTree;void getAllSum(int * sumArray,int * wArray,int len){sumArray[0] = wArray[0];for (int i = 1; i < len; i++){sumArray[i] = sumArray[i-1] + wArray[i];}}//vArray: 值数组,sumArray,概率和数组void secondOptimal(NosTree * tree,char * vArray,int * sumArray,int low,int high){int min = (int)fabs((float)(sumArray[high] – sumArray[low]));int k = low;int dw = sumArray[high] + sumArray[low-1];for (int i = low+1; i <= high; i++){int newMin = fabs(float(sumArray[high]-sumArray[i]-sumArray[i-1]));if (newMin < min){min = newMin;k = i;}}NosTree p = *tree = (NosTree)malloc(sizeof(Node));p->data = vArray[k];if (k == low){p->leftChild = NULL;}else{secondOptimal(&p->leftChild,vArray,sumArray,low,k-1);}if (k == high){p->rightChild = NULL;}else{secondOptimal(&p->rightChild,vArray,sumArray,k+1,high);}}int find(NosTree t,char key){printf("——–查找经过了:");while (t != NULL){printf("%c\t",t->data);if (t->data == key){return 1;}else if(t->data > key){t = t->leftChild;}else{t = t->rightChild;}}return 0;}void preOrderTraver(NosTree t){if (t != NULL){printf("%c\t",t->data);preOrderTraver(t->leftChild);preOrderTraver(t->rightChild);}}int _tmain(int argc, _TCHAR* argv[]){char *array= "abcdefghi";int weitht[9] = {1,1,2,5,3,4,4,3,5};int sum[9];getAllSum(sum,weitht,9);NosTree tree = NULL;secondOptimal(&tree,array,sum,0,8);printf("————-次优查找树先序遍历————–\n");preOrderTraver(tree);printf("\n————-查找h————–\n");int f = find(tree,'h');return 0;}运行截图：
而是他们在同伴们都睡着的时候，一步步艰辛地向上攀爬的。
