Как найти наименьший общий узел между двумя BST? - PullRequest
Новая
       11

Как найти наименьший общий узел между двумя BST?

1 голос
/ 05 апреля 2019

Мне нужно найти самый нижний общий узел в двух BST.У меня проблемы с поиском, как это сделать. Я должен использовать рекурсию, а не хранить значения в массивах.

Я попытался реализовать поиск по порядку.Но это не работает, так как ничего не возвращает.

Вот моя функция вставки: 

tree *insert(tree* node, int data){

    if (node == NULL) {
        node = malloc(sizeof(node));
        node->data = data;
        node->left = node->right = NULL;

    }
    else if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);

    return node;
}

Моя функция поиска. 

tree *search (tree* node, int data){
    if (node == NULL || node->data == data){
        return node;
    }
    if (data > node->data){
        return search(node->right, data);
    }
        return search(node->left, data);
}

и моя самая низкая_общая функция: 

int lowest_common (tree *t1, tree *t2){

    if(t1 == NULL || t2 == NULL){
        return -1;
    }
    if(t1->data == t2->data){
        return 1;
    }

    else if (t1->data != t2->data){
        lowest_common(t1->left, t2);
        search(t2, t1->data);
        lowest_common(t1->right, t2);
    }

    printf("test");
    return 1;
}

после вставки входных данныхв обоих деревьях я бы назвал lower_common (t1, t2)

, он должен возвращать -1, если нет общих узлов, и 1, если есть самый нижний общий узел.Но это ничего не возвращает.Есть идеи?

...