二叉排序树实现(C++封装)(2)

BinaryTree::pNode BinaryTree::SearchMinNode(pNode curNode){
    if (curNode == nullptr)
        return nullptr;
    //一直找到左子树为空的节点,即为最小值
    while (curNode->lChild != nullptr)
        curNode = curNode->lChild;
    return curNode;
}

找最大值

BinaryTree::pNode BinaryTree::SearchMaxNode(pNode curNode){
    if (curNode == nullptr)
        return nullptr;
    //一直找到右子树为空的节点,即为最大值
    while (curNode->rChild != nullptr)
        curNode = curNode->rChild;
    return curNode;
}

中序遍历

void BinaryTree::_visitMiddle(pNode root){
    if (root != nullptr){
        _visitMiddle(root->lChild);
        printf("%d;", root->data);
        _visitMiddle(root->rChild);
    }
}

void BinaryTree::VisitMiddle(){
    _visitMiddle(root);
}

删除节点
这个是最麻烦的操作,分四种情况分别处理,最麻烦的是被删节点左右子树都存在的情况,这时将被删节点内容换成其后继内容,删除其后继(递归)。

bool BinaryTree::DeleteNode(int key){
    //return _deleteNode(root, key);
    pNode node = SearchKey(key);
    if (!node)
        return false;
    //被删节点为叶子结点
    if (node->lChild == nullptr && node->rChild == nullptr){
        if (node->parent == nullptr){
            root = nullptr;
        }
        else
        {
            if (node->parent->lChild == node)
                node->parent->lChild = nullptr;
            else
                node->parent->rChild = nullptr;
        }
        delete node;
    }
    //被删节点只有左子树
    else if (node->lChild != nullptr && node->rChild == nullptr){
        //将左孩子的父亲指向被删节点的父亲
        node->lChild->parent = node->parent;
        //被删节点为根,修改根节点
        if (node->parent == nullptr)
            root = node->lChild;
        else if(node->parent->lChild == node)
            node->parent->lChild = node->lChild;
        else
            node->parent->rChild = node->lChild;
        delete node;
    }
    //被删节点只有右子树
    else if (node->lChild == nullptr && node->rChild != nullptr){
        //将右孩子的父亲指向被删节点的父亲
        node->rChild->parent = node->parent;
        //被删节点为根,修改根节点
        if (node->parent == nullptr)
            root = node->rChild;
        else if (node->parent->lChild == node)
            node->parent->lChild = node->rChild;
        else
            node->parent->rChild = node->rChild;
        delete node;
    }
    //被删节点左、右子树都有
    else {  //用后继节点取代删除节点,并删除后继
        pNode successor = SearchSuccessor(node);
        int temp = successor->data;
        DeleteNode(temp);
        node->data = temp;
    }
}

柝构函数
函数超出作用域范围时,清理占用内存。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/b69980c2a9790027ece03b3e9a62da6d.html