如何检查两个二进制树是否包含相同的节点？

Question

我正在尝试实施一个函数，该函数检查两个二进制搜索树是否相等，节点的顺序无关紧要。但是我的实施不起作用。

我不允许将树弄平成阵列。

这是我到目前为止的：

int isIdentical(struct Node* root1, struct Node* root2)
{
    
    if (root1 == NULL && root2 == NULL)
        return 1;
    
    else if (root1 == NULL || root2 == NULL)
        return 0;
    else { 
        if (root1->data == root2->data && isIdentical(root1->left, root2->left)
            && isIdentical(root1->right, root2->right))
            return 1;
        else
            return 0;
    }
}

当用包含节点的树提供时>树B = 2 5 4 6 ，输出应为：

1，这意味着它们是相等的，但是我得到了0。我不确定我出错了哪里。

这就是插入节点的方式：

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

Answer 1

制作递归treea的递归功能，并检查treeb中的每个项目是否存在。失败时，它放弃了搜索并返回0失败。 如果成功，可以是您的功能

int isIdentical(struct Node* root1, struct Node* root2)

，请再次调用treea和treeb反向的参数。 “检查现在”操作可能是迭代和内联的，因为它不需要回溯。

示例未经尝试的代码，以给出这个想法。

int isAllFound(struct Node* root1, struct Node* root2)
{
    // recursive parse of tree 1
    if (root1 == NULL)
        return 1;
    
    // iterative search of tree 2
    int found = 0;
    struct Node *root = root2;
    while(root != NULL) {
        if(root1->data == root->data) {
            found = 1;
            break;
        }
        if(root1->data < root->data)
            root = root->left;
        else
            root = root->right;
    }
    if(!found)
        return 0;
    
    // continue recursive parse of tree 1
    if(!isAllFound(root1->left, root2))
        return 0;
    if(!isAllFound(root1->right, root2))
        return 0;
    return 1;
}

然后像

if(isAllFound(treeA, treeB) && isAllFound(treeB, treeA))
    puts("Success!");

treea的每个项目一样呼叫，可以在treeb中找到，并且可以在treeb的每个项目中找到treea代码>然后它们包含相同的数据。只要钥匙是唯一的。

Answer 2

您为什么认为它们是平等的？他们不是。

树A表示为2 4 5 6，我猜您通过某种预订或级别的遍历获得了。如果您的树B（2，5，4，6）相等，则使用相同的遍历，您将获得相同的顺序。如果遍历相同，它们不等。

节点顺序无关紧要：

如果节点的顺序无关紧要。您可以做的一件事是对两种树木进行遍历遍历，然后从两者中得到一个分类的阵列。然后按元素比较两个数组元素，并声明是否相等。

Answer 3

您的功能只会将其与具有完全相同结构的2棵树相提并论。如果树的平衡方式不同，那么比较将返回0，即使值相同。

进行此比较是无关紧要的，因为如果树不平衡，树可以具有任意的深度。

您可以深入填充数组，然后以深度的一阶行走第一树，然后检查值与数组中的值相同。

这是一个简单的实现：

#include <stdlib.h>

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

size_t tree_length(const struct Node *root) {
    return root ? 1 + tree_length(root->left) + tree_length(root->right) : 0;
}

void tree_store(int *array, size_t *pos, struct Node *node) {
    if (node) {
        tree_store(array, pos, node->left);
        array[++*pos - 1] = node->data;
        tree_store(array, pos, node->right);
    }
}

int tree_check(int *array, size_t *pos, struct Node *node) {
    if (node) {
        return tree_check(array, pos, node->left)
        &&     array[++*pos - 1] == node->data
        &&     tree_check(array, pos, node->right);
    } else {
        return 1;
    }
}

/* compare trees: return 0 if different, 1 if same values, -1 if allocation error */
int isIdentical(const struct Node *root1, const struct Node *root2) {
    size_t len1 = tree_length(root1);
    size_t len2 = tree_length(root2);
    size_t pos;
    if (len1 != len2)
        return 0;

    if (len1 == 0)
        return 1;

    int *array = malloc(sizeof(*array) * len1);
    if (!array)
        return -1;
    pos = 0;
    tree_store(array, &pos, root1);
    pos = 0;
    int res = tree_check(array, &pos, root2);
    free(array);
    return res;
}

如果不允许您将树转换为数组，则可以：

• 将两种树正常化，然后使用简单的比较器，但这会修改​​树木并且很困难。
• 实现基于堆栈的迭代器，并并联两树。

这是后者的简单实现：

#include <stddef.h>

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

size_t max_size(size_t a, size_t b) {
    return a < b ? b : a;
}

size_t tree_depth(const struct Node *root) {
    return root ? 1 + max_size(tree_depth(root->left), tree_depth(root->right)) : 0;
}

int tree_next(const struct Node **stack, size_t *ppos, int *value) {
    size_t pos = *ppos;
    if (stack[pos] == NULL) {
        if (pos == 0)
            return 0;  // no more values
        pos--;
    } else {
        while (stack[pos]->left) {
            stack[pos + 1] = stack[pos]->left;
            pos++;
        }
    }
    *value = stack[pos]->data;
    stack[pos] = stack[pos]->right;
    *ppos = pos;
    return 1;
}

/* compare trees: return 0 if different, 1 if same values, -1 if allocation error */
int isIdentical(const struct Node *root1, const struct Node *root2) {
    if (root1 == NULL || root2 == NULL)
        return root1 == root2;
    size_t depth1 = tree_depth(root1);
    size_t depth2 = tree_depth(root2);
    const struct Node *stack1[depth1];
    const struct Node *stack2[depth2];
    size_t pos1 = 0;
    size_t pos2 = 0;
    stack1[pos1++] = root1;
    stack2[pos2++] = root2;
    for (;;) {
        int value1, value2;
        int has1 = tree_next(stack1, &pos1, &value1);
        int has2 = tree_next(stack2, &pos2, &value2);
        if (!has1 && !has2)
            return 1;
        if (!has1 || !has2 || value1 != value2)
            return 0;
    }
}