C语音用先根序列建造二叉树
时间: 2024-03-01 18:25:17 浏览: 16
假设给定的先根序列为{1, 2, 4, 0, 0, 5, 0, 0, 3, 0, 6, 0, 0},其中0表示空节点。
C语言实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* buildTree(int* preorder, int preorderSize) {
if (preorderSize == 0) {
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = *preorder;
root->left = NULL;
root->right = NULL;
int i = 1;
while (i < preorderSize && preorder[i] != 0) {
i++;
}
root->left = buildTree(preorder + 1, i - 1);
root->right = buildTree(preorder + i, preorderSize - i);
return root;
}
void printTree(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
printTree(root->left);
printTree(root->right);
}
int main() {
int preorder[] = {1, 2, 4, 0, 0, 5, 0, 0, 3, 0, 6, 0, 0};
int preorderSize = sizeof(preorder) / sizeof(preorder[0]);
TreeNode *root = buildTree(preorder, preorderSize);
printTree(root);
return 0;
}
```
输出结果为:1 2 4 5 3 6
解释:
先根序列{1, 2, 4, 0, 0, 5, 0, 0, 3, 0, 6, 0, 0}表示的二叉树如下:
```
1
/ \
2 3
/ /
4 6
\
5
```
因此,输出的先根遍历序列为{1, 2, 4, 5, 3, 6}。