在实际应用中，常常要考虑一个问题:如何设计一棵二叉树，使得执行路径最短，即算法的效率最高。
例1.快递包裹的邮资问题
假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹根据重量及运距进行分类从而确定邮资。
国内快递包裹资费 单位:元
(2004年1月1日起执行)
运距(公里) | 首重1000克 | 5000克以内续重每500克 | 5001克以上续重每500克 |
<=500 | 5.00 | 2.00 | 1.00 |
<=1000 >500 | 6.00 | 2.50 | 1.30 |
<=1500 >1000 | 7.00 | 3.00 | 1.60 |
<=2000 >1500 | 8.00 | 3.50 | 1.90 |
<=2500 >2000 | 9.00 | 4.00 | 2.20 |
<=3000 >2500 | 10.00 | 4.50 | 2.50 |
<=4000 >3000 | 12.00 | 5.50 | 3.10 |
<=5000 >4000 | 14.00 | 6.50 | 3.70 |
<=6000 >5000 | 16.00 | 7.50 | 4.30 |
>6000 | 20.00 | 9.00 | 6.00 |
表1 国家邮政局制定的快递包裹参考标准
根据表1可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执行的效率也不同。
铁球分类
现有一批球磨机上的铁球，需要将它分成四类:直径不大于20的属于第一类;直径大于20而不大于50的属于第二类;直径大于50而不大于100的属于第三类;其余的属于第四类;假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。
我们可以把这个判断过程表示为 图1中的两种方法:
最优二叉树算法
两种判断二叉树示意图
那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢?让我们对上述判断框做一具体的分析。
假设有1000个铁球，则各类铁球的个数分别为:100、200、300、400;
对于图7.1中的上图和下图比较的次数分别如表所示:
左图 和下图
序号 | 比较式 | 比较次数 |
1 | a<20 | 1000 |
2 | a<50 | 900 |
3 | a<=100 | 700 |
合计 | 2600 |
序号 | 比较式 | 比较次数 |
1 | a>100 | 1000 |
2 | a>50 | 600 |
3 | a<=20 | 300 |
合计 | 1900 |
表2 两种判断二叉树比较次数
过上述分析可知，图1中右图所示的判断框的比较次数远远小于左图所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。
