《Windows游戏编程大师技巧》（第二版）第11章

《Windows游戏编程大师技巧》（第二版）第11章(10) 建立二分查找树（BST）
由于应用于B树的算法在本质上是递归的，所以这一节的主题比较复杂。让我们先快速地浏览一下二叉树的一些算法，然后写一些代码，并完成一个演示程序。
与链表相似，创建BST有两种方法：树结构的根节点可以为哑元，也可以是实际有效的节点。我更喜欢以实际节点作为根节点。因此，一个空树中没有任何东西，而本应指向根节点的指针现在为NULL。
TNODE_PTR root = NULL;
Okay，要将数据插入BST，你必须确定插入数据所使用的关键字。在本例中，你可以使用人的年龄或名字。因为上面这些例子都使用年龄作为关键字，所以这里也使用年龄作为关键字。然而，以名字作为关键字更简单，你只需使用词典式的比较函数如strcmp()就可以确定名字的顺序。无论如何，下面这段代码将节点插入BST：
TNODE_PTR root = NULL; // here's the initial tree

TNODE_PTR BST_Insert_Node(TNODE_PTR root, int id, int age, char *name)
{
// test for empty tree
if (root==NULL)
   {
   // insert node at root
   root         = new(TNODE);
   root->id     = id;
   root->age    = age;
   strcpy(root->name,name);

   // set links to null
   root->right  = NULL;
   root->left   = NULL;

   printf("\nCreating tree");

   } // end if

// else there is a node here, lets go left or right
else
if (age >= root->age)
   {
   printf("\nTraversing right...");
   // insert on right branch

   // test if branch leads to another sub-tree or is terminal
   // if leads to another subtree then try to insert there, else
   // create a node and link
   if (root->right)
      BST_Insert_Node(root->right, id, age, name);
   else
      {
      // insert node on right link
      TNODE_PTR node   = new(TNODE);
      node->id     = id;
      node->age    = age;
      strcpy(node->name,name);

      // set links to null