Модульный тест AVL Tree, получить высоту узлов без родителей - PullRequest
Новая
       8

Модульный тест AVL Tree, получить высоту узлов без родителей

1 голос
/ 10 апреля 2020

Для моего школьного задания я должен реализовать вставку узла дерева AVL. У меня есть этот тестовый модуль, с 4 тестами, и 2 из них всегда терпят неудачу. Я использую две глобальные переменные, один массив для хранения чисел и одно целое число для индекса. 

int pom = 0;
int test_output[1000];

Первый тест 2 проверяет вращения с родителями: 

void test_right_rotation_with_parent() {
    //Arrange
    struct Node* root = NULL;
    int insert_nodes[] = { 15,10,5 };
    int correct_output[] = { 10,2,5,1,15,1 }; // node -> key, node -> height;
    char* passed = PASSED;

    //Act
    for (int i = 0; i < 3; i++) {
        insert(root, insert_nodes[i]);
    }

    preOrder(root);

    //Assert
    for (int i = 0; i < 6; i++) {
        if (correct_output[i] != test_output[i]) {
            passed = FAILED;
            break;
        }
    }

    printf("%s: %s\n", __func__, passed);

}

Вывод: test_right_rotation_with_parent : PASSED.

Тот же тест для левого вращения. Тогда у меня 2 теста на вращение без родителей. Это тест, который я не могу пройти. 

void test_right_rotation_without_parent() {
    //Arrange
    struct Node* root = NULL;
    int insert_nodes[] = { 20,25,15,10,5 };
    int correct_output[] = { 20,3,10,2,5,1,15,1,25,1 }; // node -> key, node -> height;
    char* passed = PASSED;

    //Act
    for (int i = 0; i < 5; i++) {
        insert(root, insert_nodes[i]);
    }

    preOrder(root);

    ...
}

Вывод: test_right_rotation_without_parent: FAILED

PreOrder: 

void preOrder(struct Node *root) {
    if (root != NULL) { // this is the main problem if a node hasn't got parent
        test_output[pom++] = root->key;
        test_output[pom++] = root->height;
        preOrder(root->link[0]); // left side
        preOrder(root->link[1]); // right side
    }
}

И это часть функции вставки, который создает узел, если раньше его не было. 

struct Node *insert(struct Node *node, int key)
{
    if (node == NULL)
    {
        struct Node *node = malloc(sizeof *node);
        if (node != NULL) 
        {

        /* if I do the same thing here which I did in preOrder,
         * the sequence of the keys will be correct,
         * however the height will always be 1 (for the without parent functions) */

            node->key = key;
            node->height = 1;
            node->link[0] = node->link[1] = NULL;
        }

        return node;
    }
    else {...}

Возможно ли заставить эту работу работать этим методом? Или мне нужно найти другой метод, если я хочу пройти эти испытания?

...