Кодирование функции remove () для двоичного дерева

Question

Я нахожусь в классе структур данных, и мы должны кодировать двоичное дерево (не двоичное дерево поиска). У меня примерно 90% работает, но у меня возникают проблемы с работой моей функции remove ().

Для справки, мы создаем класс BinaryTree, который должен иметь следующие функции

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 (который был нам предоставлен):

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 не избавляется от узла -только ценность. Так, например, вызов метода moveValuesUpTree (2) для дерева с выходным значением (по порядку) 74625381 будет 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