5-7 麻烦老师帮我看一下非递归实现是否正确

Question

Key minimum(){
    assert(count>0);
    Node* current = root;
    while(current->left!=null){
        current = current->left;
    }
    return current->key;
}

void removeMin(){
    assert(count>0);
    Node* current = root;
    Node* parent = null;
    while(current->left!=null){
        parent = current;
        current = current->left;
    }
    if(parent!=null){
        parent->left = current->right;
    }
    delete current;
    count--;
}

不知道写得对不对，也想知道removeMin有没有更简便的写法。谢谢老师

Answer 1

liuyubobobo 2022-04-07 03:40:16

这个代码有问题。如果最小值是 root 会出问题。比如：

1
 \
  2
   \
    3

测试一下试试看？

继续加油！：）

• 提问者 慕运维2948618 #1

  我检查了一下，不过minimum应该没写错吧？
  removeMin确实存在如老师所说的这种情况。
  由于原问题不能修改，我将修正后的代码写在回答上了，希望老师能再次审阅，谢谢。

• liuyubobobo 回复 提问者 慕运维2948618 #2

  这次没有问题了，继续加油！：）

• 提问者 慕运维2948618 #3

  非常感谢！

Answer 2

提问者 慕运维2948618 2022-04-07 09:11:07

void removeMin(){
    assert(count>0);
    Node* current = root;
    Node* parent = null;
    while(current->left!=null){
        parent = current;
        current = current->left;
    }
    if(parent!=null){
        parent->left = current->right;
    }else{
        root = root->right;
    }
    delete current;
    count--;
}