C语言先序和中序序列都为N个结点建立二叉树_生成二叉树代码
时间: 2024-03-02 10:51:58 浏览: 19
好的,下面是 C 语言的代码实现:
首先,我们需要定义二叉树的结构体:
```
typedef struct TreeNode {
char data; // 节点数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
```
然后,我们可以定义一个函数来构建二叉树:
```
TreeNode *buildTree(char *preorder, char *inorder, int len) {
if (len == 0) { // 如果序列长度为0,则返回NULL
return NULL;
}
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode)); // 创建根节点
root->data = *preorder; // 根节点为先序遍历的第一个节点
int rootIndex = 0; // 找到根节点在中序遍历中的位置
while (rootIndex < len && *(inorder + rootIndex) != *preorder) {
rootIndex++;
}
int leftLen = rootIndex; // 左子树的长度
int rightLen = len - rootIndex - 1; // 右子树的长度
root->left = buildTree(preorder + 1, inorder, leftLen); // 递归构建左子树
root->right = buildTree(preorder + 1 + leftLen, inorder + rootIndex + 1, rightLen); // 递归构建右子树
return root;
}
```
在这个函数中,我们首先判断序列长度是否为0,如果是则返回 NULL。然后,我们创建根节点,并将其数据设置为先序遍历的第一个节点。接着,我们在中序遍历中找到根节点的位置,根据根节点的位置,我们可以计算出左子树的长度和右子树的长度。然后,我们分别递归构建左子树和右子树,并将其作为根节点的左子树和右子树。
最后,我们可以调用这个函数来构建二叉树:
```
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
int len = sizeof(preorder) / sizeof(char);
TreeNode *root = buildTree(preorder, inorder, len);
return 0;
}
```
在这个例子中,我们使用先序遍历为 `ABDECFG`,中序遍历为 `DBEAFCG` 的序列构建二叉树。