、二叉树
  树应用及其广泛,二叉树是树中的一个重要类型。在这里,我们主要研究二叉树的一种应用方式:判定树。其主要应用在描述分类过程和处理判定优化等方面上。
  在人工智能中,通常有很多分类判断。现在有这样一个例子:设主角的生命值d,在省略其他条件后,有这样的条件判定:当怪物碰到主角后,怪物的反应遵从下规则:
  
 
表1
   根据条件,我们可以用如下普通算法来判定怪物的反应:  if(d<100) state=嘲笑,单挑;
  else if(d<200) state=单挑;
    else if(d<300) state=嗜血魔法;
      else if(d<400) state=呼唤同伴;
        else state=逃跑;  上面的算法适用大多数情况,但其时间性能不高,我们可以通过判定树来提高其时间性能。首先,分析主角生命值通常的特点,即预测出每种条件占总条件的百分比,将这些比值作为权值来构造最优二叉树(哈夫曼树),作为判定树来设定算法。假设这些百分比为: 
表2
   构造好的哈夫曼树为: 
图2
   对应算法如下:  if(d>=200)&&(d<300) state=嗜血魔法;
  else if(d>=300)&&(d<500) state=呼唤同伴;
    else if(d>=100)&&(d<200) state=单挑;
      else if(d<100) state=嘲笑,单挑;
        else state=逃跑;  通过计算,两种算法的效率大约是2:3,很明显,改进的算法在时间性能上提高不少。
  一般,在即时战略游戏中,对此类判定算法会有较高的时间性能要求,大家可以对二叉树进行更深入的研究。现在,我们进入本文的最后一节:图的介绍,终于快要完事了。