Удаление элемента из дерева, С++

#дерево #бинарное_дерево #алгоритм #cpp

Написал алгоритм удаления элемента из бинарного дерева поиска. Алгоритм не рекурсивный.
Так как это академическая задачка, требуют рекурсивный. Рекурсивный метод у меня не
выходит. Код выкладывать смысла нет. Если у кого есть простой и понятный рекурсивный
алгоритм удаления элемента из бинарного дерева поиска, буду благодарен.     

Ответы

Ответ 1

Если взять такое определение бинарного дерева.
class BinaryTreeNode {
public:
    BinaryTreeNode() : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(-1) {}
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}
public: 
    static int getDepth(BinaryTreeNode * node) {
        int left = 0, right = 0;
        left = getDepth(node->leftChild);
        return 0;
    }
public:
    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

То алгоритм может выглядеть так:
void DeleteNodeFromBinary(BinaryTreeNode * node, int value)
{
    if (node == NULL)
        return;

    if (value < node->value)
        return DeleteNodeFromBinary(node->leftChild, value);
    else if(value > node->value)
        return DeleteNodeFromBinary(node->rightChild, value);
    else  {
        if(node->leftChild == NULL && node->rightChild == NULL) {
            if (node->parent->leftChild == node) 
                node->parent->leftChild = NULL;
            else      
                node->parent->rightChild = NULL;
            delete node;
        } else {
            BinaryTreeNode * newnode = NULL;
            if(node->leftChild != NULL) {
                newnode = Rightmost(node->leftChild);
            } else                    
                newnode = Leftmost(node->rightChild);

            if (node->parent->leftChild == node) 
                node->parent->leftChild = newnode;
            else      
                node->parent->rightChild = newnode;

            newnode->parent = node->parent;
            newnode->rightChild = node->rightChild;
            newnode->leftChild = node->leftChild;

            delete node; 
        }
    }
}
BinaryTreeNode * Leftmost(BinaryTreeNode * node) {
    if (node == NULL)
        return NULL;
    if (node->leftChild != NULL) {
        return Leftmost(node->leftChild);
    }
    return node;
}
BinaryTreeNode * Rightmost(BinaryTreeNode * node) {
    if (node == NULL)
        return NULL;
    if (node->rightChild != NULL) {
        return Rightmost(node->rightChild);
    }
    return node;
}