次優查找樹的原理是什麼？

typedef struct TNode
{
int data;
struct TNode* lchild;
struct TNode* rchild;
}BiTree, *pBiTree;

void creat_tree(pBiTree rt)
{
char ch;
ch=getchar();
if("#"==ch)
{
rt=NULL;
}
else
{
rt=(pBiTree)malloc(sizeof(BiTree));
rt-&>data=ch;
creat_tree(rt-&>lchild); //構造左子樹
creat_tree(rt-&>rchild); //構造右子樹
}
}

void PreOrderPrint(pBiTree rt)
{
cout &<&< "PreOrderPrint: "; if(!rt) return; stack& s;
s.push(rt);
while(!s.empty())
{
pBiTree cur = s.top();
cout &<&< (char)(cur-&>data);
s.pop();
if(cur-&>rchild)
s.push(cur-&>rchild);
if(cur-&>lchild)
s.push(cur-&>lchild);
}
cout &<&< "@" &<&< endl; } void InOrderPrint(pBiTree rt) { cout &<&< "InOrderPrint: "; if(!rt) return; stack& s;
pBiTree cur = rt;

while(!s.empty() || cur != NULL)
{
while(cur)
{
s.push(cur);
cur = cur-&>lchild;
}
if(!s.empty())
{
cur = s.top();
cout &<&< (char)(cur-&>data);
s.pop();
cur = cur-&>rchild;
}
}
cout &<&< "@" &<&< endl; } bool visit(pBiTree node) { if(node) { cout &<&< char(node-&>data);
return 1;
}
else
return 0;
}

void LevelOrderPrint(pBiTree rt)
{
cout &<&< "LevelOrderPrint: "; if(!rt) { cout &<&< "@" &<&< endl; return; } queue& q;
q.push(rt);
pBiTree cur = NULL;

void AssignVal(int* val, int low, int high, int factor)
{
if(!val || low &< 0 || low &> high)
return;
if(low == high)
{
val[low] = factor;
return;
}
int mid = (low + high) / 2;
val[mid] = factor;
AssignVal(val, low, mid-1, factor+1);
AssignVal(val, mid+1, high, factor+1);
}

int* SearchLength(int len)
{
if(len &<= 0) return NULL; int* sl = (int*)malloc(sizeof(int) * len); if(!sl) exit(0); AssignVal(sl, 0, len-1, 1); return sl; } float* SumWeight(int* nodes, float* prob, int size) { float* sw = (float*)malloc(sizeof(float) * size); if(!sw) exit(0); float before = 0.0; for(int i = 0; i &< size; i++) { sw[i] = nodes[i] * prob[i] + before; before = sw[i]; } return sw; } void SecondOptimal(pBiTree rt, int* nodes, float* sw, int low, int high) { if(!nodes || !sw || low &< 0 || low &> high)
return;
int i = low;
float min = fabs(sw[high] - sw[low]);
float dw = sw[high];
for(int j = low + 1; j &<= high; ++j) { float tmp = fabs(dw - sw[j] - sw[j-1]); if(tmp &< min) { i = j; min = tmp; } } rt = (pBiTree)malloc(sizeof(BiTree)); if(!rt) exit(0); rt-&>data = nodes[i];
if(i == low)
rt-&>lchild = NULL;
else
SecondOptimal(rt-&>lchild, nodes, sw, low, i-1);
if(i == high)
rt-&>rchild = NULL;
else
SecondOptimal(rt-&>rchild, nodes, sw, i+1, high);
}

int main(int argc, char const *argv[])
{
//1、已知條件，待查找的有序數組和數組中各元素被查找的概率(不等概率)
const int size = 5;
int nodes[size] = {"1","2","3","4","5"};
float probability[size] = {0.2,0.3,0.2,0.1,0.2};

//2、根據數組，求出每個元素查找成功時的平均查找長度（次數），存儲在schlen數組中。
int* schlen = SearchLength(size);

//3、求出每個元素的權值sw，由待查數組nodes和schlen中下標相對的元素相乘得到。
float* sw = SumWeight(schlen, probability, size);

//4、然後根據書中的演算法，遞歸的構造次優查找樹
pBiTree root;
SecondOptimal(root, nodes, sw, 0, size - 1);