c++二叉树解决八枚硬币问题代码

下面是用 C 语言实现二叉树解决八枚硬币问题的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int left;
    int right;
    struct Node *left_child;
    struct Node *right_child;
} Node;

Node* create_tree(int left, int right) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->left = left;
    node->right = right;
    node->left_child = NULL;
    node->right_child = NULL;
    return node;
}

void destroy_tree(Node *root) {
    if (root != NULL) {
        destroy_tree(root->left_child);
        destroy_tree(root->right_child);
        free(root);
    }
}

void solve_coin_problem(Node *node) {
    if (node->left == 1 && node->right == 1) {
        printf("Left coin is fake!\n");
        return;
    }
    if (node->left + node->right == 2) {
        printf("Right coin is fake!\n");
        return;
    }
    int left_weight = 0;
    int right_weight = 0;
    for (int i = node->left; i <= node->left + (node->right - node->left) / 2 - 1; i++) {
        left_weight += i;
    }
    for (int i = node->left + (node->right - node->left) / 2; i <= node->right; i++) {
        right_weight += i;
    }
    if (left_weight == right_weight) {
        printf("Both coins are real!\n");
        return;
    }
    if (left_weight < right_weight) {
        solve_coin_problem(node->left_child);
    } else {
        solve_coin_problem(node->right_child);
    }
}

int main() {
    Node *root = create_tree(1, 8);
    root->left_child = create_tree(1, 4);
    root->right_child = create_tree(5, 8);
    solve_coin_problem(root);
    destroy_tree(root);
    return 0;
}

这里使用了一个 `Node` 结构体来表示二叉树的节点，包含了左、右硬币编号、左子树和右子树指针。`create_tree` 函数用于创建节点，`destroy_tree` 函数用于销毁节点。`solve_coin_problem` 函数用于解决硬币问题，其中使用了二分法来比较左右两边硬币的重量。在 `main` 函数中创建了一个二叉树并解决了硬币问题。