用C语言编写函数,能够根据指定序列(例如先序序列)创建二叉树。
时间: 2024-03-23 21:36:36 浏览: 61
可以使用递归来实现根据先序序列创建二叉树的函数。具体步骤如下:
1. 定义二叉树节点的结构体
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
2. 编写递归函数,根据先序序列创建二叉树
```c
TreeNode* createTree(int* preorder, int preorderSize) {
static int index = 0; // 记录先序序列中的当前节点位置
if (index >= preorderSize || preorder[index] == -1) { // 如果当前节点为空节点,则返回 NULL
index++;
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = preorder[index++]; // 根据当前位置创建节点
node->left = createTree(preorder, preorderSize); // 递归创建左子树
node->right = createTree(preorder, preorderSize); // 递归创建右子树
return node;
}
```
3. 在主函数中调用该函数创建二叉树
```c
int main() {
int preorder[] = {1, 2, -1, -1, 3, 4, -1, -1, 5, -1, -1};
int preorderSize = sizeof(preorder) / sizeof(int);
TreeNode* root = createTree(preorder, preorderSize);
return 0;
}
```
在上述代码中,先序序列中的空节点用 -1 表示。函数会先根据当前位置创建节点,然后递归创建左子树和右子树。当遍历到空节点时,返回 NULL。最后在主函数中调用该函数即可创建二叉树。
阅读全文