假设按关键字从小到大有序排列的记录序列为
{
,
,…,
}其中
.key
< .key
< … < .key与其相应的权值序列为
{
,
,…,
}构造次优查找树的方法是：从关键字序列中选取第
个记录作为次优二叉树的"根结点"，要求 
取最小值，即
然后分别对子序列 {
,,…,
}和{
,
,…,}
构造次优查找树，分别作为根的左子树和右子树。算法描述请见下页。
为便于计算，引入记录序列的"累计权值和"为
，并设
=0
和 
则可得到如下的结果：
