c++ - 数据结构:关于二叉查找树(BinarySearchTree)的删除算法的疑问?
天蓬老师
天蓬老师 2017-04-17 11:18:16
0
2
601

Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构,关于删除的代码是这样的:

// 删除以t为根的BST中值为x的节点
void remove(int x, BinaryNode*& t)
{
    if ( t == NULL)
    {
        return ;
    }
    if (x < t->data)
    {
        remove(x, t->left);
    }
    else if (x > t->data)
    {
        remove(x, t->right);
    }
    // 左右都有节点的情况
    else if (t->left != NULL && t->right != NULL)
    {
        t->data = findMin(t->right)->data; // 右子树最小的节点
        remove(t->data, t->right);
    }
    else
    {
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right);
        delete oldNode;
    }
}

二叉树的基本性质是节点大于其左子树的所有节点,小于其右子树的所有节点,
在这个删除算法中,当删除的节点有2个儿子的情况的时候,为什么是从右子树找出最小的节点而不是从左子树找出最大的节点呢?

天蓬老师
天蓬老师

欢迎选择我的课程,让我们一起见证您的进步~~

人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート
私たちについて 免責事項 Sitemap
PHP中国語ウェブサイト:福祉オンライン PHP トレーニング,PHP 学習者の迅速な成長を支援します!