用c语言己知一棵二叉树的前序序列和中序序列分别存于两个一维数组中,试编写 算法建立该二叉树的二叉链表。。
时间: 2024-05-04 07:20:16 浏览: 180
以下是使用C语言实现二叉树的建立算法,根据给定的前序和中序遍历序列:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
TreeNode* buildTree(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
TreeNode* root = malloc(sizeof(TreeNode));
root->data = preorder[preStart];
int inorderRootIndex = inStart;
while (inorder[inorderRootIndex] != root->data) {
inorderRootIndex++;
}
int leftSubtreeSize = inorderRootIndex - inStart;
root->left = buildTree(preorder, preStart + 1, preStart + leftSubtreeSize, inorder, inStart, inorderRootIndex - 1);
root->right = buildTree(preorder, preStart + leftSubtreeSize + 1, preEnd, inorder, inorderRootIndex + 1, inEnd);
return root;
}
void printInorder(TreeNode* root) {
if (root == NULL) {
return;
}
printInorder(root->left);
printf("%d ", root->data);
printInorder(root->right);
}
int main() {
int preorder[] = {1, 2, 4, 5, 3, 6, 7};
int inorder[] = {4, 2, 5, 1, 6, 3, 7};
int size = sizeof(preorder) / sizeof(preorder[0]);
TreeNode* root = buildTree(preorder, 0, size - 1, inorder, 0, size - 1);
printInorder(root);
return 0;
}
```
这个算法的时间复杂度是O(n),其中n是二叉树中节点的数量。
阅读全文