首页 > 编程语言 > 详细

算法导论中对二叉树链表中 Delete 函数的实现

时间:2015-03-03 15:07:21      阅读:400      评论:0      收藏:0      [点我收藏+]

上一篇博客中对 Delete 函数的实现是根据被删除节点子节点的子节点个数, 分为无子节点, 一个子节点和两个子节点的情况分别考虑的。

而这次的代码是根据算法导论的实现用 C++ 直译过来的, 代码如下:

void BinarySearchTree::Delete (const int32_t& value)
{
    auto node = Search (value);
    if (node == nullptr) {
        cerr << "There is no such value!\n";
        return;
    }

    PTreeNode successor = 
        (node->leftChild == nullptr || node->rightChild == nullptr)
            ? node
            : Successor (node);

    
    PTreeNode successorChild =
        (successor->rightChild != nullptr)
            ? successor->leftChild
            : successor->rightChild;

    if (successorChild != nullptr){
        successorChild->parent = successor->parent;
    }

    if (successor->parent.expired()) {
        root = successorChild;
    }
    else {
        auto successorParent = successor->parent.lock ();
        if (successor == successorParent->leftChild) {
            successorParent->leftChild = successorChild;
        }
        else {
            successorParent->rightChild = successorChild;
        }
    }

    if (node != successor) {
        node->key = successor->key;
    }
}

 

算法导论中对二叉树链表中 Delete 函数的实现

原文:http://www.cnblogs.com/wuOverflow/p/4310912.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!