C语言假设二叉树的结点值是字符,根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。
时间: 2024-01-23 15:10:03 浏览: 23
好的,根据您的问题,我可以给您提供以下的 C 语言代码,其中包括了建立二叉树的函数和打印二叉树的函数:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的结构体
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree(char* preorder, int* index) {
char val = preorder[*index];
if (val == '#') {
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
(*index)++;
node->left = createTree(preorder, index);
(*index)++;
node->right = createTree(preorder, index);
return node;
}
// 打印二叉树
void printTree(TreeNode* root) {
if (root == NULL) {
printf("# ");
return;
}
printf("%c ", root->val);
printTree(root->left);
printTree(root->right);
}
int main() {
char preorder[] = "ABD##E##CF##G##";
int index = 0;
TreeNode* root = createTree(preorder, &index);
printf("先序遍历序列为:%s\n", preorder);
printf("生成的二叉树为:");
printTree(root);
printf("\n");
return 0;
}
```
这段代码中,我们首先定义了一个二叉树的结构体,其中包含了二叉树结点的值和左右子树的指针。然后,我们编写了一个 `createTree()` 函数来根据输入的先序遍历序列建立一棵二叉树。在函数中,我们首先读取当前的结点值,如果是字符 '#',则说明该结点为空,返回 NULL。否则,我们就创建一个新的结点,并将当前的值赋给它。然后,我们递归地调用 `createTree()` 函数来分别创建它的左子树和右子树,并将它们的指针分别赋给当前结点的 `left` 和 `right` 字段。最后,我们返回当前结点的指针。
接着,我们编写了一个 `printTree()` 函数来打印先序遍历序列。在函数中,我们首先判断当前结点是否为空,如果是,则打印字符 '#',表示该结点为空。否则,我们就打印当前结点的值,并递归地调用 `printTree()` 函数来打印它的左子树和右子树。
最后,在 `main()` 函数中,我们定义了一个先序遍历序列,然后调用 `createTree()` 函数来建立一棵二叉树,并调用 `printTree()` 函数来打印它。