合并两个树

预设条件

  • 接收两个BST返回一个BST
  • 左子树的最大值小于右子树的最小值
  • 返回一个排序好的BST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
JoinTrees(t1,t2):
   Input trees t1,t2
   Output t1 and t2 joined together

   if t1 is empty then return t2
   else if t2 is empty then return t1
   else
      curr=t2,parent=NULL
      while curr->left is not NULL do
         parent=curr
         curr=curr->left
      end while
      if parent is not NULL then
         parent->left=curr->right
         curr->right=t2
      end if
      curr-left=t1
      return curr
   end if

从BST中删除节点

  • 如果BST为空：删不了

  • 如果没有子树：待删节点本身就是叶子节点，直接删就可以

  • 如果只有一边的子树：用唯一的子树替换待删节点即可

  • 两棵子树：

    • 版本1：当成合并两棵子树处理

    • 版本2：将当前节点的右孩子置为新的root，将左孩子交给右子树的最小节点接管

仅展示版本2的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// delete an item from a Tree
Tree TreeDelete(Tree t, Item it) {
    if (t != NULL) {
        if (it < data(t))
            left(t) = TreeDelete(left(t), it);
        else if (it > data(t))
            right(t) = TreeDelete(right(t), it);
        else {
            Tree new;
            if (left(t) == NULL && right(t) == NULL)
                new = NULL;
            else if (left(t) == NULL)    // if only right subtree, make it the new root
                new = right(t);
            else if (right(t) == NULL)   // if only left subtree, make it the new root
                new = left(t);
            else                         // left(t) != NULL and right(t) != NULL
                new = joinTrees(left(t), right(t));
            free(t);
            t = new;
        }
    }
    return t;
}

右旋

1
2
3
4
5
6
7
8
9
10
rotateRight(n1):
   Input tree n1
   Output n1 rotated to the right

   if n1 is empty or n1->left is empty then
      return n1
   n2 = n1->left
   n1->left=n2->right
   n2->right=n1
   return n2

左旋

1
2
3
4
5
6
7
8
9
10
rotateLeft(n1):
   Input tree n1
   Output n1 rotated to the left

   if n1 is empty or n1->right is empty then
      return n1
   n2 = n1->right
   n1->right=n2->left
   n2->left=n1
   return n2

快来参与讨论吧~