Блог

Главная - Вопросы по программированию - C — создание двоичного класса дерева поиска, один узел исчезает после поворота

C — создание двоичного класса дерева поиска, один узел исчезает после поворота

#c #rotation #binary-tree

#c #вращение #двоичное дерево

Вопрос:

Я пытаюсь создать пользовательское двоичное дерево поиска, и у меня все сделано, кроме функции поворота, которая, похоже, не перемещает узел. Функция rotate вызывается только при поиске и обнаружении узла, и если у узла есть правильный дочерний элемент. Для простоты я добавлю только функции, которые используются в этом, чтобы сделать его короче:

 #include <iostream>

using namespace std;

template <typename T>
class MRBST {
public:
    MRBST();
    ~MRBST();

    void push(const T amp;);
    bool search(const T amp;);
    void PrintPreorder();
private:
    struct Node {
        T data;
        Node *left;
        Node *right;

        Node (const T amp; theData, Node *lt, Node *rt) 
        : data(theData), left(lt), right(rt) {}
    };
    Node *root;

    void push(const T amp;, Node * amp;) const;
    void remove(const T amp;, Node * amp;) const;
    Node* findMin(Node *t) const {
        if (t == NULL) {
            return NULL;
        }
        if (t->left == NULL) {
            return t;
        }
        return findMin(t->left);
    }
    void preorder(Node * amp;);
    bool search(const T amp;, Node *);
    Node* findNode(const T amp; x, Node * t) {
        if (t == NULL) {
            return NULL;
        }
        if (x < t->data) {
            return findNode(x, t->left);
        } else if (x > t->data) {
            return findNode(x, t->right);
        } else if (x == t->data) {
            return t;
        }
        return NULL;
    }
    void rotate(Node *);
};

template <typename T>
void MRBST<T>::PrintPreorder() {
    preorder(root);
    cout << endl;
}

template <typename T>
void MRBST<T>::preorder(Node * amp; t) {
    if (t != NULL) {
        cout << t->data << endl;
        preorder(t->left);
        preorder(t->right);
    }
}

template <typename T>
bool MRBST<T>::search(const T amp; x) {
    if (search(x, root)) {
        Node *temp = findNode(x, root);
        rotate(temp);
        return true;            
    } else {
        return false;
    }
}

template <typename T>
void MRBST<T>::rotate(Node * k1) {
    if (k1->right == NULL) {
        return;
    } else {
        Node *temp = k1->right;
        k1->right = temp->left;
        temp->left = k1;
    }
}


template <typename T>
bool MRBST<T>::search(const T amp; x, Node *t) {
    if (t == NULL) {
        return false;
    } else if (x < t->data) {
        return  search(x, t->left);
    } else if (x > t->data) {
        return search(x, t->right);
    } else {
        return true;
    }
}

У меня есть простой файл тестирования, который просто добавляет некоторые числа в дерево, а затем выполняет поиск, после чего распечатывается в предварительном порядке.

 #include <iostream>
#include "MRBST.h"

using namespace std;

int main() {
    MRBST<int> binaryTree;
    binaryTree.push(5);
    binaryTree.push(20);
    binaryTree.push(3);
    binaryTree.push(3);
    binaryTree.push(4);
    binaryTree.push(22);
    binaryTree.push(17);
    binaryTree.push(18);
    binaryTree.push(8);
    binaryTree.push(9);
    binaryTree.push(1);
    binaryTree.PrintPreorder();
    cout << endl;
    binaryTree.search(17);
    binaryTree.PrintPreorder();
    cout << endl;

}

С выводом, выглядящим примерно так:

5
3
1
4
20
17
8
9
18
22

5
3
1
4
20
17
8
9
22

Если бы кто-нибудь мог дать некоторое представление о том, что происходит не так с моей функцией поворота, это было бы большим подспорьем.

Ответ №1:

Почему вы выполняете rotate поиск? Он должен быть доступен только для чтения.

Из-за этого вы теряете узел.

Посмотрите на свой rotate :

     Node *temp = k1->right;
    k1->right = temp->left;
    temp->left = k1;

Предположим, что k1 = x имеет right = y и left = z, смотрите шаг за шагом:

     Node *temp = k1->right;

temp =k1-> right = y, k1 = x, k1->left = z

     k1->right = temp->left;

k1-> right = ?, k1-> left = z, temp = y

     temp->left = k1;

k1-> right = ?, k1-> left = z, temp-> left = x.

Теперь — куда пошел Y? Вы его потеряли.

Комментарии:

1. просто то, что должно быть сделано в нашем назначении. Как это доступно только для чтения?

2. @Muller — search возвращает true , если найдено, false в противном случае. Какое назначение?

3. @Muller, на самом деле теперь, когда я смотрю на это — я не знаю, что вы search должны делать. В любом случае, ваш rotate ошибочен.

4. Разве k1-> right не будет просто тем, что temp-> left? Итак, поскольку temp = k1-> right, то это то же самое, что и k1-> right = k1-> right-> left. Если k1-> right-> left равно NULL, то разве это не просто установило бы k1-> right как NULL?

5. @Muller, да, это так. Но никто не указывает на него, поэтому он потерян для вас.

Ответ №2:

Внимательно посмотрите на свою функцию rotate(), шаг за шагом, чтобы увидеть, выполняет ли она то, что вы хотите, или нет.

Метки: ,