c - 如何找到两个 BST 之间的最低公共节点？

Question

我需要在两个 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;
}

在两棵树中插入输入后，我会调用 minimum_common(t1, t2)

如果没有公共节点，它应该返回 -1，如果有公共的最低节点，它应该返回 1。但它什么也不返回。有任何想法吗？

标签： cbinary-search-tree