|
《Windows游戏编程大师技巧》（第二版）第11章(12) root = BST_Insert_Node(root, 4, 30, "jim");
图11-10示意了如何将“Jim”插入一个树中。
图11-10：在BST中插入元素
将新节点插入BST这一过程的执行效率和在BST中搜索节点相当，因此，一次插入操作所需的平均时间约为O(log2n)，而最坏的情况是O(n)（当关键字以降序线性排列时）。
搜索BST
一旦建立了BST，就是进行数据的搜索的时候了。当然这会用到许多递归处理方法，应加以关注。搜索BST有三种方法：
• 前序——访问节点、然后按前序搜索左子树，最后按前序搜索右子树。
• 中序——按中序搜索左子树，然后访问节点，最后按中序搜索右子树。
• 后序——按后序搜索左子树，然后按后序搜索右子树，最后访问节点。
注意 左和右是任意的，关键在于访问和搜索的顺序。
参见图11-11。该图显示了一个简单的二叉树及三种搜索顺序。
图11-11：前序、中序、后序搜索方式的节点访问次序
知道了这三种顺序，你可以为之编写相当简单的递归算法来实现它们。当然，遍历二叉搜索树的目的是找到目标并将其返回。下面的函数便实现了二叉树遍历的功能。你可以为之增加停止代码以便搜索到目标关键字时结束程序。不过，现在你比较在意搜索方法：
void BST_Inorder_Search(TNODE_PTR root)
{
// this searches a BST using the inorder search // test for NULL
if (!root)
return; // traverse left tree
BST_Inorder_Search(root->left); // visit the node
printf("name: %s, age: %d", root->name, root->age); // traverse the right tree
BST_Inorder_Search(root->right); } // end BST_Inorder_Search 以下是前序搜索代码：
void BST_Preorder_Search(TNODE_PTR root)
{
// this searches a BST using the preorder search // test for NULL
if (!root)
return; // visit the node
printf("name: %s, age: %d", root->name, root->age); // traverse left tree
BST_Inorder_Search(root->left); // traverse the right tree
BST_Inorder_Search(root->right); } // end BST_Preorder_Search 以下是后序搜索代码：
void BST_Postorder_Search(TNODE_PTR root)
{
// this searches a BST using the postorder search // test for NULL
if (!root)
return; // traverse left tree
BST_Inorder_Search(root->left); // traverse the right tree
BST_Inorder_Search(root->right); // visit the node
printf("name: %s, age: %d", root->name, root->age); } // end BST_Postorder_Search 就这么简单，像不像变戏法？假设你已建立了一棵二叉树，试着用这个调用进行中序遍历。
BST_Inorder_Search(my_tree);
| 
