Question

12.1 二叉查找树

12.1-2

二叉查找树：左子树关键字<根结点关键字<右子树关键字

堆：左子树关键字<根结点关键字 && 右子树关键字<根结点关键字

不能，因为一个结点的的左子树与右子树的关键字大小没有关系

12.1-3

用栈实现：见 算法导论-10.4-有根树的表示 中的 10.4-3

不用栈实现：见 算法导论-10.4-5

12.1-4

//递归的先序遍历  
void BST_Tree::Preorder_Tree_Walk(BST_Node *x)  
{  
  //x 不是叶子结点  
  if(x != NULL)  
  {  
    //访问当前结点  
    cout<<x->key<<' ';  
    //先序遍历当前结点的左子树  
    Preorder_Tree_Walk(x->left);  
    //先序遍历当前结点的右子树  
    Preorder_Tree_Walk(x->right);  
  }  
}
//递归的后序遍历  
void BST_Tree::Postorder_Tree_Walk(BST_Node *x)  
{  
  //x 不是叶子结点  
  if(x != NULL)  
  {  
    //后序遍历当前结点的左子树  
    Postorder_Tree_Walk(x->left);  
    //后序遍历当前结点的右子树  
    Postorder_Tree_Walk(x->right);  
    //访问当前结点  
    cout<<x->data<<' ';  
  }  
}

12.2 查询二叉查找树

12.2-1
c，e
12.2-2
//递归地查找最小值  
BST_Node *BST_Tree::Tree_Minimum(BST_Node *x)  
{  
  if(x->left != NULL)  
    return Tree_Minimum(x->left);  
  else return x;  
}  
//递归的查找最大值  
BST_Node *BST_Tree::Tree_Maximum(BST_Node *x)  
{  
  if(x->right != NULL)  
    return Tree_Maximum(x->right);  
  else return x;  
} 
12.2-3
//查找中序遍历下 x 的前驱，即小于 x 的最大值  
BST_Node *BST_Tree::Tree_Predecessor(BST_Node *x)  
{  
  //如果 x 的左子树非空  
  if(x->left != NULL)  
    //x 的前驱是 x 的左子树的最大值  
    return Tree_Maximum(x->left);  
  //如果 x 的左子树为空且 x 有前驱 y，那么 y 是 x 的最低祖先结点，且 y 的右儿子也是  
  BST_Node *y = x->p;  
  while(y != NULL && x == y->left)  
  {  
    x = y;  
    y = y->p;  
  }  
  return y;  
}  
12.2-4
（1）
4->left = 2 4->right =NIL
2->left = 1 2->right = 3
搜索路径 4-2-1
（2）
1->right = 3 1->left = NUL
3->left = 2 3->right = 4
搜索路径 1-3-4

12.3 插入和删除

12.3-1

//递归的二叉查找树的插入操作，分三种情况  
void BST_Tree::Tree_Insert(BST_Node *x, BST_Node *z)  
{  
  //已经存在  
  if(z->key == x->key)  
  {  
    cout<<"error:exist"<<endl;  
    return;  
  }  
  //插入到 x 的左子树中  
  else if(z->key < x->key)  
  {  
    //x 没有左子树  
    if(x->left == NULL)  
    {  
      //修改指针，插入操作  
      x->left = z;  
      z->p = x;  
      return;  
    }  
    //x 有左子树  
    else  
      //对 x 的左子树执行插入操作  
      Tree_Insert(x->left, z);  
  }  
  //插入到 x 的右子树中，与上面类似  
  else if(z->key > x->key)  
  {  
    if(x->right == NULL)  
    {  
      x->right = z;  
      z->p = x;  
    }  
    else  
      Tree_Insert(x->right, z);  
  }  
} 

12.3-3

最坏是 n^2

最好是 nlgn

12.3-4

求 y 的前驱 z 分为两种情况，以下分别讨论：

（1）y 有左孩子，则 z 是 left[y]中最右边的结点，z 没有右孩子，因此删除 z 时直接删除修改指针即可，没有问题

（2）y 没有左孩子，则 z 是 y 的祖先，y 是 z 右子树是最左边的点，又分为两种情况：

（2.1）若 z 没有左孩子，则直接删除 z 并修改指针，没有问题。

（2.2）若 z 有左孩子，则不直接删除 z，而是用 z 代替 y 存在并删除 y。这里会有问题，另一个数据结构中的保存了指向 y 的指针，但是 y 的内容转移到另一个结点上了，指向 y 的指针指向了一个被释放的空间。

解决方法：使 TREE-DELETE 返回删除后的 y 的指针，这个值可能会变，可能不变。让另一个数据结构的 y 指针指向 TREE-DELETE 的返回值。

12.3-5

不或交换，反例如图

12.3-6

当待删除结点有两个子树时，不删除待删除结点，而是删除它的前驱或后继，用随机数 rand()%2 来确定删除的前驱还是后继

代码见文：二