1.若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上
A.√    B.×

正确答案：B

2.若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小值一定在叶结点上
A.√    B.×

正确答案：A

上面两道题，对比起来，很好地反映了二叉搜索树的特性。

3.二叉搜索树的插入和删除操作

  1. BinTree Insert( BinTree BST, ElementType X )
  2. {
  3.     if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
  4.         BST = (BinTree)malloc(sizeof(struct TNode));
  5.         BST->Data = X;
  6.         BST->Left = BST->Right = NULL;
  7.     }
  8.     else { /* 开始找要插入元素的位置 */
  9.         if( X < BST->Data )
  10.             BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
  11.         else  if( X > BST->Data )
  12.             BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
  13.         /* else X已经存在，什么都不做 */
  14.     }
  15.     return BST;
  16. }
  18. BinTree Delete( BinTree BST, ElementType X )
  19. {
  20.     Position Tmp;
  22.     if( !BST )
  23.         printf(“要删除的元素未找到”);
  24.     else {
  25.         if( X < BST->Data )
  26.             BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
  27.         else if( X > BST->Data )
  28.             BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
  29.         else { /* BST就是要删除的结点 */
  30.             /* 如果被删除结点有左右两个子结点 */
  31.             if( BST->Left && BST->Right ) {
  32.                 /* 从右子树中找最小的元素填充删除结点 */
  33.                 Tmp = FindMin( BST->Right );
  34.                 BST->Data = Tmp->Data;
  35.                 /* 从右子树中删除最小元素 */
  36.                 BST->Right = Delete( BST->Right, BST->Data );
  37.             }
  38.             else { /* 被删除结点有一个或无子结点 */
  39.                 Tmp = BST;
  40.                 if( !BST->Left )       /* 只有右孩子或无子结点 */
  41.                     BST = BST->Right;
  42.                 else                   /* 只有左孩子 */
  43.                     BST = BST->Left;
  44.                 free( Tmp );
  45.             }
  46.         }
  47.     }
  48.     return BST;
  49. }

这段代码给我很大启发的主要就是删除函数里面对左右都有孩子的节点处理，这里很巧妙地把它转换成：用左边最大的节点来替换原来的值并用没有右孩子的节点删除方式，把拿去替换的那个节点从被替换节点的左子树里面删除掉。这里利用了二叉搜索树最大节点一定没有右孩子的性质，同理，我们也可以利用二叉搜索树最小节点没有左孩子的性质来完成删除有左右孩子的节点的任务。