C语言假设二叉树的结点值是字符,根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。
时间: 2024-01-23 17:10:08 浏览: 62
根据带空指针的先序遍历结果建立二叉树
以下是一个简单的 C 语言程序,用于根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* createNode(char val) {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
struct TreeNode* buildTree(char* preorder, int* index) {
char val = preorder[*index];
(*index)++;
if (val == '#') {
return NULL;
}
struct TreeNode* node = createNode(val);
node->left = buildTree(preorder, index);
node->right = buildTree(preorder, index);
return node;
}
struct TreeNode* createTree(char* preorder) {
int index = 0;
return buildTree(preorder, &index);
}
void printTree(struct TreeNode* root) {
if (root == NULL) {
printf("# ");
return;
}
printf("%c ", root->val);
printTree(root->left);
printTree(root->right);
}
int main() {
char* preorder = "ABD###CE##F";
struct TreeNode* root = createTree(preorder);
printTree(root);
return 0;
}
```
这个程序定义了一个 `TreeNode` 结构体,包含一个字符值、一个指向左子节点的指针和一个指向右子节点的指针。`createNode` 函数用于创建一个新的节点,`buildTree` 函数用于递归地构建一棵二叉树,`createTree` 函数用于初始化一棵二叉树,`printTree` 函数用于输出一棵二叉树的先序遍历序列。在 `main` 函数中调用 `createTree` 函数创建一棵二叉树,并调用 `printTree` 函数输出其先序遍历序列。在 `buildTree` 函数中,使用一个整数指针 `index` 来记录当前正在处理的节点的位置。如果当前节点的值是 '#',则返回 NULL,否则创建一个新的节点,并递归地构建其左子树和右子树。
阅读全文