用C语言实现二叉树的链式存储结构,可根据给定的序列,创建相应的二叉树。
时间: 2024-09-27 14:08:06 浏览: 29
在C语言中,我们可以使用结构体来实现二叉树的链式存储结构。首先,我们需要定义一个`Node`结构体,它包含两个指针分别指向左孩子和右孩子,以及一个用于存储节点值的数据域。下面是基本的实现步骤:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int data; // 节点数据
struct TreeNode* left; // 左子节点
struct TreeNode* right; // 右子节点
} Node;
// 插入函数,根据顺序创建二叉树
Node* insert(Node* root, int value) {
if (root == NULL) { // 如果根节点为空,新建一个节点
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (value < root->data) { // 向左递归插入
root->left = insert(root->left, value);
} else { // 向右递归插入
root->right = insert(root->right, value);
}
return root;
}
// 根据给定数组构建二叉搜索树
Node* buildBST(int arr[], int start, int end) {
if (start > end) {
return NULL;
}
int mid = (start + end) / 2;
Node* root = insert(NULL, arr[mid]);
root->left = buildBST(arr, start, mid - 1);
root->right = buildBST(arr, mid + 1, end);
return root;
}
// 示例:输入有序数组[1, 2, 3, 4, 5],创建二叉搜索树
int main() {
int values[] = {1, 2, 3, 4, 5};
int size = sizeof(values) / sizeof(values[0]);
Node* root = buildBST(values, 0, size - 1);
// 打印整个二叉树(这里仅作示例,实际操作可能需要其他遍历算法)
printf("Binary Search Tree:\n");
printInOrder(root); // 假设有一个printInOrder函数来按照中序遍历打印树
return 0;
}
```
阅读全文