|
《Windows游戏编程大师技巧》（第二版）第11章(9) 例如，看一下程序DEMO11_2.CPPEXE。该程序实现了阶乘算法。注意一下阶乘的溢出速度。看看你的机器能计算到多大阶乘。绝大多数的机器可以计算到69！不骗你。
数学 我们来递归地实现一下菲波那契Fibonacci算法。第n个Fibonacci数列元素fn=fn-1+fn-2，另外，f0=0，f1=1，那么，f2=f1+f0=1，f3=f2+f1=2。所以整个Fibonacci序列为：0，1，1，2，3，5，8，13…数一数向日葵中一圈圈的种子数目，恰好是Fibonacci序列。 树结构
接下来我们要讨论的高级数据结构是：树结构（tree）。通常人们使用递归算法来处理树结构，因此我在上面论述中特别提到了递归。图11-6图示了一些不同的树状数据结构。 图11-6：树的拓扑结构
人们发明树结构，用于储存和搜索海量的数据。最常见的树结构是二叉树，也叫作B-树或二分查找树（BST）。树结构是从单一根节点发散出的树状结构，包含许多子节点。每个节点可以派生出一个或两个子节点（兄弟节点，Sibling），二叉树因此而得名。而且我可以讨论一个二叉树的阶（Order），即该树一共有几层。图11-7所示的是不同层次的二叉树。
图11-7：一些不同阶的二叉树
关于树结构，有趣的是信息查询的速度很快。绝大多数二叉树使用单一的关键字来查询数据。例如，假定你想创建一个包含游戏对象记录的二叉树，且每一个游戏对象具有多个属性，你可能会使用游戏对象的创建时间作为关键字，或将数据库中的每一节点定义为代表一个人。下面是可以用来保存单个人的节点的数据结构：
typedef struct TNODE_TYP
{
int age; // age of person
char name[32]; // name of person
NODE_TYP *right; // link to right node
NODE_TYP *left; // link to left node
} TNODE, *TNODE_PTR;
注意树节点与链表节点的相似之处！它们之间惟一的不同是使用数据结构并构造树的方法。看一看上例，假如有五个对象（人），其年龄分别为5、25、3、12和10。图11-8表示包含该数据的两个不同的二叉树。不过，你可以做得更好，比如在插入算法中根据数据插入顺序来维持二叉树的某种属性。 图11-8：数据集合 年龄 {5，25，3，12，10} 的二叉树编码
注意
Of course, the data in this example can be anything you want.
当然，在本例中，数据可以定义为任何值。 注意在建立如图11.8所示的二叉树时，使用了如下约定：任一节点的右子节点总是大于或等于该节点本身，左子节点总是小于其本身。你还可以使用其他的约定，只要保持一致性。
二叉树可以存储海量数据，而且应用“二分查找法”可以快速地检索数据。这是二叉树的优越性所在。比如，如果一个二叉树带有一百万个节点，至多进行20次比较便可以检索到数据！这是不是棒极了？其原因在于检索中的每次迭代，搜索空间的节点数都减少一半。从根本上说，假如有n个节点，那么平均搜索次数为log2 n，运行时间为O(log2 n)。
注意
上述所说的搜索时间只适于平衡二叉树——即每一层次均含有相等的左右子节点的二叉树。如果二叉树不是平衡的，那么它就退化为一个链表，而搜索时间也退化为一个线性函数。 B树第二个非常酷的属性是你可以定位子树并单独处理它。该子树仍然具有B树的所有属性。因此，如果你知道检索的位置，便可以搜索子树检索你所需要的东西。这样一来，你便可以创建树的树，或建立子树的索引表，而不必处理整个树。这在3D场景建模中是非常重要的。你可以为整个游戏空间建立一个树结构，而以数百棵子树来表示空间中的各个房间。你还可以创建另一个树结构来指代具有偏序排列的指向子树根指针的链表。如图11-9所示。有关这方面更多的内容会在本书的以后章节中论及。 图11-9：在B树结构上使用一个二级索引表
最后，让我们谈一谈何时使用树结构。我建议，当所处理的问题或数据类似于树结构时使用树结构。比方说，当你随手画出问题的草图，而发现其中具有左右分支的话，树结构明显应该是合适的。
| 
