在给定广义表表示的情况下实现二叉树的生成,以二叉链表的形式存储,写出C语言代码
时间: 2024-12-17 10:56:44 浏览: 9
数据结构C语言版期末题库.doc
在C语言中,我们可以使用递归的方式将广义表转换为二叉树的结构,每个节点包含两个指针(指向左子节点和右子节点),而广义表通常是以列表形式存储的。下面是一个简单的示例,假设广义表的元素是整数,我们创建一个`Node`结构体表示二叉树节点:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data; // 节点数据
struct Node* left; // 左子节点
struct Node* right; // 右子节点
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode) {
newNode->data = value;
newNode->left = newNode->right = NULL;
}
return newNode;
}
// 从广义表生成二叉树(这里假设表只有一个元素)
TreeNode* buildTreeFromList(int* list, int size) {
if (size == 0 || list == NULL)
return NULL;
TreeNode* root = createNode(list[0]);
if (size > 1) {
root->left = buildTreeFromList(list + 1, size / 2);
root->right = buildTreeFromList(list + size / 2 + 1, size - size / 2);
}
return root;
}
// 打印二叉树遍历
void printInorder(TreeNode* node) {
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main() {
int list[] = {1, 2, 3, 4, 5, 6, 7}; // 示例广义表
int size = sizeof(list) / sizeof(list[0]);
TreeNode* tree = buildTreeFromList(list, size);
// 测试打印结果
printf("In-order traversal of the binary tree:\n");
printInorder(tree);
return 0;
}
```
这个代码片段首先定义了一个`Node`结构表示二叉树节点,并实现了创建节点、构建二叉树和中序遍历的功能。注意,这只是一个基础版,实际应用中需要处理更复杂的广义表情况,比如列表长度不固定或非连续等。
阅读全文