根据先序序列、中序序列建立二叉树,给出c代码示例
时间: 2023-12-08 20:52:02 浏览: 41
以下是根据先序序列和中序序列建立二叉树的C代码示例:
```
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int findIndex(int *inorder, int inorderSize, int val) {
for (int i = 0; i < inorderSize; i++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
struct TreeNode* buildTreeHelper(int* preorder, int preorderSize, int* inorder, int inorderSize, int preStart, int inStart, int inEnd) {
if (preStart >= preorderSize || inStart > inEnd) {
return NULL;
}
struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
node->val = preorder[preStart];
int index = findIndex(inorder, inorderSize, preorder[preStart]);
node->left = buildTreeHelper(preorder, preorderSize, inorder, inorderSize, preStart + 1, inStart, index - 1);
node->right = buildTreeHelper(preorder, preorderSize, inorder, inorderSize, preStart + index - inStart + 1, index + 1, inEnd);
return node;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
if (preorder == NULL || inorder == NULL || preorderSize != inorderSize) {
return NULL;
}
return buildTreeHelper(preorder, preorderSize, inorder, inorderSize, 0, 0, inorderSize - 1);
}
```
其中,`buildTreeHelper`函数是递归建立二叉树的辅助函数,`findIndex`函数用于寻找根节点在中序数组中的索引。`buildTree`函数是主函数,调用`buildTreeHelper`函数建立二叉树,并返回树的根节点。