3

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

1 ответ 1

6

Если взять такое определение бинарного дерева.

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;
}
1
  • >> return DeleteNodeFromBinary(node->leftChild, value);<br> Зачем вы вставляете return? Меня немного это смущает, ведь без него получится тоже самое.
    – psyhitus
    Commented 15 янв. 2011 в 14:52

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.