为二叉树编写 remove() 函数

Question

我在数据结构中 class，我们必须编写二叉树（不是二叉搜索树）代码。我有大约 90% 的工作正常，但我无法让我的 remove() 功能正常工作。

作为参考，我们正在制作一个必须具有以下功能的 class 二叉树

template <class ItemType>
class BinaryTree {
    private:
     std::shared_ptr<BinaryNode<ItemType>> rootptr;

    protected:
     // Removes the target value from the tree
     virtual std::shared_ptr<BinaryNode<ItemType>
     removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
                  const ItemType& target, bool isSuccessful);

     // Copies values up the tree to overwrite value in current
     // node until a leaf is reached; the leaf is then removed,
     // since its value is stored in the parent.
     std::shared_ptr<BinaryNode<ItemType>>
     moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>
                      subTreePtr);

      // other { working } methods

    public:
     // Removes specified item from the tree
     bool remove(const ItemType& data);

     // other { working } methods
}

BinaryNode class（提供给我们）的接口是：

template <class ItemType>
class BinaryNode {
    private:
     ItemType item;
     std::shared_ptr<BinaryNode<ItemType>> leftChildPtr;
     std::shared_ptr<BinaryNode<ItemType>> rightChildPtr;
    public:
     // returns true if node has no children
     bool isLeaf() const;

     // other typical methods (constructors, getters, setters)
}

到目前为止，我已经为我的 moveValuesUpTree 函数尝试了以下实现：

std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::
    moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>
                     subTreePtr) {

    if(subTreePtr) {
        if(!subTreePtr->isLeaf()) {
            if(subTreePtr->getLeftChildPtr()) {
                subTreePtr->setItem(subTreePtr->getLeftChildPtr()
                                    ->getItem());
                moveValuesUpTree(subTreePtr->getLeftChildPtr());
            } else if(subTreePtr->getRightChildPtr()) {
                subTreePtr->setItem(subTreePtr->getRightChildPtr()
                                    ->getItem());
                moveValuesUpTree(subTreePtr->getRightChildPtr());
            } // end if
        } // end if
    } // end if
    return subTreePtr;
} // end moveValuesUpTree

此函数用于将值向上移动到树中。我在想，在编写 removeValue() 函数时，我可以将要删除的节点的值移动到树的底部，然后将其删除（这样它始终是一片叶子，您不必担心重新连接任何节点），但是 moveValuesUpTree 函数删除了我想要删除的值。有没有办法在上面的递归 moveValuesUpTree 函数中保留这个值，然后将它存储在叶子中？或者有没有更好的方法来结合使用这两个受保护的方法来删除值？

谢谢！

编辑：moveValuesUpTree 函数不会删除节点——只是删除值。因此，例如，在（后序）输出为 74625381 的树上调用 moveValuesUpTree(2) 将是 77645831。

Answer 1

与其将值移动到最后一个叶子然后删除叶子，不如在向上移动值时将其删除，因为此时您将找到叶子并知道其确切位置。我的建议是测试当前节点的左或右子节点是否是叶子，如果是，则删除它，因为您已经将它的值移动到当前节点中。

std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::
moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>subTreePtr) {

    if(subTreePtr) {
        if(!subTreePtr->isLeaf()) {
            if(subTreePtr->getLeftChildPtr()) {
                subTreePtr->setItem(subTreePtr->getLeftChildPtr()->getItem());

                if(subTreePtr->getLeftChildPtr()->isLeaf())
                    //Delete left child here
                else
                    moveValuesUpTree(subTreePtr->getLeftChildPtr());
              } else if(subTreePtr->getRightChildPtr()) {
                subTreePtr->setItem(subTreePtr->getRightChildPtr()->getItem());

                if(subTreePtr->getRightChildPtr()->isLeaf())
                    //Delete right child here
                else
                     moveValuesUpTree(subTreePtr->getRightChildPtr());
            } // end if
        } // end if
    } // end if
    return subTreePtr;
} // end moveValuesUpTree

Answer 2

感谢@Matriac，我通过编辑 moveValuesUpTree

解决了这个问题

std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::
    moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>>
                     subTreePtr) {

    if(subTreePtr) {
        if(!subTreePtr->isLeaf()) {
            if(subTreePtr->getLeftChildPtr()) {
                subTreePtr->setItem(subTreePtr->getLeftChildPtr()
                                    ->getItem());
                if(subTreePtr->getLeftChildPtr()->isLeaf()) {
                    subTreePtr->setLeftChildPtr(nullptr);
                } else {
                    moveValuesUpTree(subTreePtr->getLeftChildPtr());
                }
             } else if(subTreePtr->getRightChildPtr()) {
            subTreePtr->setItem(subTreePtr->getRightChildPtr()
                                ->getItem());
                if(subTreePtr->getRightChildPtr()->isLeaf()) {
                    subTreePtr->setRightChildPtr(nullptr);
                } else {
                    moveValuesUpTree(subTreePtr->getRightChildPtr());
                } // end if
            } // end if
        } // end if
    } // end if
    return subTreePtr;
} // end moveValuesUpTree

为二叉树编写 remove() 函数

Coding remove() function for a Binary Tree

c++

recursion

binary-tree