用c++输入广义表建立二叉树

这里给出一个简单的例子，可以通过输入广义表来建立二叉树：

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

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

Node* createNode(char data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Node* createTree(char* str, int* index) {
    if (str[*index] == '\0') {
        return NULL;
    }
    Node* node = NULL;
    if (str[*index] != '(' && str[*index] != ')') {
        node = createNode(str[*index]);
    }
    (*index)++;
    if (str[*index] == '(') {
        (*index)++;
        node->left = createTree(str, index);
    }
    if (str[*index] == ')') {
        (*index)++;
        return node;
    }
    if (str[*index] == '(') {
        (*index)++;
        node->right = createTree(str, index);
    }
    return node;
}

void printTree(Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%c", root->data);
    if (root->left || root->right) {
        printf("(");
        printTree(root->left);
        printf(",");
        printTree(root->right);
        printf(")");
    }
}

int main() {
    char str[] = "A(B(C),D)";
    int index = 0;
    Node* root = createTree(str, &index);
    printf("The binary tree is: ");
    printTree(root);
    printf("\n");
    return 0;
}

在这个例子中，我们定义了一个 `Node` 结构体来表示二叉树的节点，其中包含了数据和左右子节点的指针。然后定义了一个 `createNode` 函数用于创建节点，一个 `createTree` 函数用于根据广义表创建二叉树，一个 `printTree` 函数用于输出二叉树。

在 `createTree` 函数中，我们首先判断当前字符是否为 `(` 或 `)`，如果不是，就创建一个节点，并让指针指向该节点。然后递归调用 `createTree` 函数构建它的左右子树。最后返回该节点。

在 `main` 函数中，我们简单地输入了一个广义表，然后调用 `createTree` 函数创建二叉树，并调用 `printTree` 函数输出二叉树。输出结果为：

The binary tree is: A(B(C,),D)

可以看到，我们成功地根据广义表创建了一个二叉树，并成功地输出了它。