比较两个二叉搜索树

Question

我想做的是比较两个二叉搜索树。这是为了计算在它们身上发生的重复次数。

首先，我添加了这个在二叉搜索树中查找特定元素的函数。

node *search(node **tree, char val)
{
    if (!(*tree))
    {
        return NULL;
    }

    if (val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if (val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if (val == (*tree)->data)
    {
        return *tree;
    }
}

然后我想遍历其中一棵树并与每个元素进行比较，但它不起作用。

int countRepetition(node *tree, node *secondTree)
{
    node *tempCount;
    tempCount = search(&secondTree, tree->data);
    if (tempCount->data < tree->data)
    {
        countRepetition(tree->left, tempCount);
    }
    else if (tempCount->data > tree->data)
    {
        countRepetition(tree->right, tempCount);
    }
    else if (tempCount->data == tree->data)
    {
        return 1;
    }
    return 0;
}

例如，我期望的是：如果第一棵树上有 a、b、c、d，第二棵树上有 a、d、m、k，那么函数应该 return2。如果有人帮助我，我会很高兴，我快死了，因为我是 C 语言的新手。

这是全部代码

#include <stdlib.h>
#include <stdio.h>
typedef struct bin_tree
{
    char data;
    struct bin_tree *right, *left;
} node;
void insert(node **tree, char val)
{
    node *temp = NULL;
    if (!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if (val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    } 
    else if (val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }
}
node *search(node **tree, char val)
{
    if (!(*tree))
    {
        return NULL;
    }

    if (val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if (val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if (val == (*tree)->data)
    {
        return *tree;
    }
}

int countRepetition(node *tree, node *secondTree)
{
    node *tempCount;
    tempCount = search(&secondTree, tree->data);
    if (tempCount->data < tree->data)
    {
        countRepetition(tree->left, tempCount);
    }
    else if (tempCount->data > tree->data)
    {
        countRepetition(tree->right, tempCount);
    }
    else if (tempCount->data == tree->data)
    {
        return 1;
    }
    return 0;
}

char main(char argc, char const *argv[])
{
    node *root, *secondRoot;
    node *tmp;

    root = NULL;
    /*Here i create the first tree*/
    insert(&root, 'a');
    insert(&root, 'b');
    insert(&root, 'c');
    insert(&root, 'd');
    insert(&root, 'j');
    insert(&root, 'k');
    insert(&root, 'z');
    //Here i create the second tree
    insert(&secondRoot, 'p');
    insert(&secondRoot, 'b');
    insert(&secondRoot, 'f');
    insert(&secondRoot, 'd');
    insert(&secondRoot, 'g');
    insert(&secondRoot, 'k');
    insert(&secondRoot, 'h');

    printf("\n%d\n", countRepetition(root, secondRoot));

    return 0;
}

Answer 1

此处存在一些重大错误

首先你的代码没有在这里初始化 root 和 secondRoot

 node *root, *secondRoot;

应该是

    node* root = NULL, * secondRoot = NULL;

下一行

 tempCount = search(&secondTree, tree->data);

不检查是否返回 NULL，所以下一行

 if (tempCount->data < tree->data)

在这种情况下失败。

请注意，不需要双指针传递，这会使您的代码很难阅读。您只需要在实际分配根节点的插入位置使用它。所有其他调用都不会更改传入的树指针。我会有一个 'createTree' 函数，returns 一个空树，然后插入不需要那个特殊情况代码

但主要是 - 学习使用调试器。

Answer 2

一些问题：

main声明错误。应该是：
```
int main(int argc, char const *argv[])
```
secondRoot 未初始化。它应该初始化为 NULL
search 在进行递归调用后没有 return 值。递归调用的结果应该return。
search 不需要 pointer-pointer 参数。由于它不改变树，假设它是它的根，它只需要一个 single-pointer 参数。
countRepetition 应该检查 tempCount 是否为 NULL，以避免 tempCount->data.
的未定义行为
假设 search return 是一个具有搜索值或 NULL 的节点，测试 tempCount->data > tree->data 和tempCount->data < tree->data 没有意义。这些不应该是真的。
countRepetition中只有return语句return0或1，所以这个函数不可能return另一个整数值。
看起来你想实现一些二进制搜索，但这意味着即使上面的几点被纠正，你也永远不会访问第一棵树中的所有节点，所以你很可能会缺少一些匹配值。

时间复杂度

您的想法似乎是访问第一棵树中的每个值，并在第二棵树中对每个值执行搜索，然后计算匹配项。如果我们称第一棵树的节点数，和第二棵树的节点数，那么这就代表了一个O(log)的时间复杂度。

对于小树，这很好，但如果和都很大，我们可以做得更好。我们可以按排序顺序（即中序遍历）迭代第一棵树中的值，并对第二棵树也这样做，同时。当它是两个当前访问的节点中较小的一个时，我们将转到两个遍历之一中的下一个节点。通过这种方式，我们“串联”穿过两棵树。由于访问是按价值排序的，因此我们一定会以这种方式找到相等的价值。

此替代算法的时间复杂度为 O(+)。当和具有相同的数量级时，这比第一种算法提供的时间复杂度更好。

实施

我建议创建一种用于按顺序访问节点的迭代器，这样您就可以随时请求该遍历中节点的后继节点。为此，您需要一个堆栈（例如链表），以便了解哪些是仍需要访问的当前节点的祖先。

这是需要为该方面添加的代码：

// Stack implementation
typedef struct node_list
{
    struct bin_tree *node;
    struct node_list *next;
} nodeList;

void pushFront(nodeList **head, node *newNode) {
    nodeList *newHead = malloc(sizeof(nodeList));
    newHead->node = newNode;
    newHead->next = *head;
    *head = newHead;
}

node *popFront(nodeList **head) {
    nodeList *front = *head;
    node *frontNode = front->node;
    *head = front->next;
    free(front);
    return frontNode;
}

// Inorder tree iterator implementation
nodeList *treeIterator(node *root) {
    if (root == NULL) return NULL;
    nodeList *head = NULL;
    pushFront(&head, root);
    // Push path to left-most node (which has least value)
    while (root->left != NULL) {
        root = root->left;
        pushFront(&head, root);
    }
    return head;
}

node *next(nodeList **head) {
    if (*head == NULL) return NULL;
    node *currentNode = popFront(head);
    node *nextNode = currentNode;
    if (nextNode->right != NULL) {
        nextNode = nextNode->right;
        pushFront(head, nextNode);
        while (nextNode->left != NULL) {
            nextNode = nextNode->left;
            pushFront(head, nextNode);
        }
    }
    return currentNode;
}

实际的算法可以这样实现：

int countRepetition(node *tree, node *secondTree)
{
    int count = 0;
    
    nodeList *iterator1 = treeIterator(tree);
    nodeList *iterator2 = treeIterator(secondTree);

    node *node1 = next(&iterator1);
    node *node2 = next(&iterator2);
    while (node1 != NULL && node2 != NULL) {
        if (node1->data < node2->data) {
            node1 = next(&iterator1);
        } else if (node1->data > node2->data) {
            node2 = next(&iterator2);
        } else {
            count++;
            node1 = next(&iterator1);
            node2 = next(&iterator2);
        }
    }
    return count;
}

这里是 search 函数的修复（见上面的评论）：

node *search(node *tree, char val)
{
    if (tree == NULL)
    {
        return NULL;
    }

    if (val < tree->data)
    {
        return search(tree->left, val);
    }
    else if (val > tree->data)
    {
        return search(tree->right, val);
    }
    else if (val == tree->data)
    {
        return tree;
    }
}

不要忘记在 main 中初始化 secondTree = NULL，并释放树使用的内存（我会把它留给你处理）。

比较两个二叉搜索树

Comparing two binary search tree

c

windows

recursion

gcc

binary-search-tree

时间复杂度

实施