用C语言编写完整函数代码程序,能够根据先序序列给{34,18,76,52,13,67,82,25,58,91,73,20}创建二叉树.
时间: 2024-11-27 20:07:31 浏览: 15
在C语言中,我们可以使用递归的方式来构建二叉搜索树(BST)。这里提供了一个完整的函数,它接受一个整数数组作为先序遍历的结果,然后创建对应的二叉搜索树:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建一个新的二叉树节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!newNode) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->val = val;
newNode->left = newNode->right = NULL;
return newNode;
}
// 根据先序遍历构建二叉树
TreeNode* buildTreePreorder(int* preorder, int n) {
if (n <= 0)
return NULL;
// 先序遍历的第一个元素是根节点
TreeNode* root = createNode(preorder[0]);
if (root == NULL)
return NULL;
// 从第二个元素开始,递归地为左子树和右子树构造二叉树
root->left = buildTreePreorder(&preorder[1], n / 2);
root->right = buildTreePreorder(&preorder[n / 2 + 1], n - n / 2 - 1);
return root;
}
// 测试代码
int main() {
int values[] = {34, 18, 76, 52, 13, 67, 82, 25, 58, 91, 73, 20};
int n = sizeof(values) / sizeof(values[0]);
TreeNode* root = buildTreePreorder(values, n);
if (root != NULL) {
// 输出二叉树结构(这里仅做展示,实际操作需要其他方法)
printf("Binary Tree created:\n");
inorderTraversal(root);
} else {
printf("Failed to create binary tree.\n");
}
return 0;
}
// 中序遍历用于展示二叉树结构
void inorderTraversal(TreeNode* node) {
if (node == NULL)
return;
inorderTraversal(node->left);
printf("%d ", node->val);
inorderTraversal(node->right);
}
```
这个程序首先定义了一个二叉树节点结构,然后实现了创建节点和根据先序遍历构建二叉树的功能。`buildTreePreorder`函数会递归地找到每个节点的位置并将它们插入到树中。在`main`函数中,我们测试了这个过程。
阅读全文