C语言代码实现广义表建立二叉树（运用栈）

在C语言中，我们可以利用栈来构建广义表并将其转换成二叉树。广义表通常表示层次结构的数据，而二叉树是一种特殊的广义表，每个节点最多有两个子节点。下面是一个简单的示例，展示如何通过递归的方式将广义表转换为二叉树：

首先，我们需要定义一个结构体来表示节点和栈元素：

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

typedef struct TreeNode {
    int data;        // 节点数据
    struct TreeNode* left;   // 左子树
    struct TreeNode* right;  // 右子树
} TreeNode;

typedef struct StackNode {
    TreeNode* node;
    int index;
} StackNode;

// 创建一个新的栈节点
StackNode* createStackNode(TreeNode* node, int index) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->node = node;
    newNode->index = index;
    return newNode;
}

// 栈的基本操作，例如压入、弹出等
void push(StackNode** top, TreeNode* node, int index) {
    *top = createStackNode(node, index);
}

TreeNode* pop(StackNode** top) {
    if (*top == NULL)
        return NULL;
    StackNode* temp = *top;
    *top = (*top)->next;
    free(temp);
    return temp->node;
}

接下来，我们编写函数`buildTreeFromList`来处理广义表到二叉树的转换：

TreeNode* buildTreeFromList(StackNode* top, int listLength) {
    if (top == NULL || top->index >= listLength)
        return NULL;

    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = top->node->data;

    // 遇到左孩子，压入栈继续递归处理左子树
    if (top->node->left != NULL)
        push(&top, top->node->left, top->index + 1);

    // 递归处理右子树
    TreeNode* right = buildTreeFromList(top->next, listLength);
    root->right = right;

    return root;
}

最后，你可以这样使用这个函数：

int main() {
    // 假设有一个广义表存储在数组list[]中，listLength为其长度
    int list[] = {1, 2, 3, 4, 5, 6, 7};
    int listLength = sizeof(list) / sizeof(list[0]);

    StackNode* top = NULL;
    TreeNode* root = buildTreeFromList(&top, listLength);

    // 现在root就是从广义表创建的二叉树的根节点
    // ... 打印或进一步处理二叉树 ...

    return 0;
}