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

《Windows游戏编程大师技巧》（第二版）第11章(11)       node->left   = NULL;
      node->right  = NULL;

      // now set right link of current "root" to this new node
      root->right = node;
      printf("\nInserting right.");

      } // end else

   } // end if
else // age < root->age
   {
   printf("\nTraversing left...");
   // must insert on left 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->left)
      BST_Insert_Node(root->left, id, age, name);
   else
      {
      // insert node on left link
      TNODE_PTR node   = new(TNODE);
      node->id     = id;
      node->age    = age;
      strcpy(node->name,name);

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

      // now set right link of current "root" to this new node
      root->left = node;

      printf("\nInserting left.");
      } // end else

} // end else

// return the root
return(root);

} // end BST_Insert_Node
首先你要测试是否是空树，如果是空树就创建其根节点。如有必要，应使用最先插入BST的那项内容创建根节点。因此，最先被插入BST的那项内容或记录就代表搜索空间中靠近中间的项，以便树能很好地平衡。总之，如果树有超过一个的节点，你必须遍历该树，至于将节点插入左子树或右子树则取决于你要插入的记录。当你遇到树结构的叶节点或终止枝时，便可以将新节点插入该处。