实现BST相等判断与子树检测后has_subtree返回错误，求原因

我尝试实现两个二叉搜索树（BST）相关功能：一是判断两棵BST是否完全相同，二是判断一棵BST是否包含另一棵BST作为完整子树（包含所有后代节点）。最初编写的代码返回错误结果，随后我更新了代码（包含insert、level_order函数，修正后的compare_bst、has_subtree函数及main测试逻辑），但has_subtree函数依旧返回错误结果，希望排查问题原因。

初始代码 #

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


int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        compare_bst(root_p->left, root_q->left);
        compare_bst(root_p->right, root_q->right);
    }
    return 1;
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        has_subtree(root->left, sub_root);
        has_subtree(root->right, sub_root);
    }
    return 0;
}

更新后代码 #

Node* insert(Node* root, int elm) { // -V
    if (!root) {
        root = create_node_bst(elm);
    }
    else if (elm <= root->data) {
        root->left = insert(root->left, elm);
    }
    else {
        root->right = insert(root->right, elm);
    }
    return root;
}

void level_order(Node* root) { // visit all children before grand children [BFS]
    if (!is_empty(root)) {
        Queue *q = malloc(sizeof *q);
        if (q) {
            *q = queue_init;
            enqueue(q, root);
            while (!is_empty_q(q)) {
                Node* cur = front(q);
                printf("%d ", cur->data);
                if (cur->left != NULL)
                    enqueue(q, cur->left);
                if (cur->right != NULL)
                    enqueue(q, cur->right);
                dequeue(q);
            }
        }
        free(q);
    }
}

int compare_bst(Node* root_p, Node* root_q) {
    if (root_p && root_q) {
        if (root_p->data != root_q->data)
            return 0;
        return compare_bst(root_p->left, root_q->left) && compare_bst(root_p->right, root_q->right);
    }
    return !root_p && !root_q;
}

int has_subtree(Node* root, Node* sub_root) {
    if (root){
        if (compare_bst(root, sub_root))
            return 1;
        return has_subtree(root->left, sub_root) || has_subtree(root->right, sub_root);
    }
    return 0;
}

int main() {
    #define MAX 7
    int n = MAX;
    BST bst1 = bst_init;
    BST bst2 = bst_init;
    Node* bst1_root = bst1.root;
    Node* bst2_root = bst2.root;
    int arr[MAX] = {4, 1, 2, 3, 6, 7, 9};
    for (int i = 0; i < n; i++) {
        bst1_root = insert(bst1_root, arr[i]);
       // bst2_root = insert(bst2_root, arr[i]);
        if (i > 4) {
            bst2_root = insert(bst2_root, arr[i]);
        }
       // else
    //         bst2_root = insert(bst2_root, 9);      
    }
        
    
    printf("bst1 and bst2 are the same: %d \n", compare_bst(bst1_root, bst2_root));
    printf("bst1_root has bst2 subtree: %d", has_subtree(bst1_root, bst2_root));
}

问题排查分析 #

初始代码核心错误 #

• compare_bst：递归调用左右子树后未返回结果，导致无论子树是否匹配，最终都会返回1，完全忽略子树的匹配状态。
• has_subtree：递归遍历左右子树时未传递匹配结果，仅当根节点直接匹配时返回1，否则遍历后直接返回0，丢失了子树中存在匹配的情况。

更新后代码的潜在问题 #

修正后的compare_bst逻辑正确，但has_subtree仍返回错误结果，大概率是以下原因：

1. create_node_bst未正确初始化节点指针

如果创建节点时没有将left和right显式设为NULL，节点的左右指针会是随机垃圾值。这会导致compare_bst在判断子节点是否为空时出错——明明应为空的子节点被判定为非空，最终返回匹配失败。

正确的节点创建函数示例：

Node* create_node_bst(int elm) {
    Node* new_node = malloc(sizeof(Node));
    new_node->data = elm;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

2. BST结构体初始化错误

如果bst_init的定义未将root设为NULL（比如#define bst_init {}），那么bst2.root会是随机值，初始的bst2_root非空，插入节点时逻辑混乱，导致bst2结构错误。

3. 测试数据的结构验证缺失

可以通过level_order函数打印两棵树的结构，确认bst2的结构是否符合预期（根7，右子树9），以及bst1中对应子树的结构是否一致。

修复建议 #

1. 确保create_node_bst显式初始化节点的left和right为NULL。
2. 确认bst_init的定义正确，例如#define bst_init {NULL}。
3. 打印树的结构，验证两棵树的实际形态是否符合预期。

内容的提问来源于stack exchange，提问作者v_head