假设二叉树的结点值是字符,根据输入的一棵二叉树的扩展先序遍历序列建立一棵以二叉链表表示的二叉树。用c语言写
时间: 2024-01-23 13:39:28 浏览: 79
用C创建表达式二叉树
以下是用C语言实现建立二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
// 执行递归建树
TreeNode* buildTree(char* str, int* index) {
if (str[*index] == '\0' || str[*index] == '#') {
++(*index);
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = str[*index];
++(*index);
node->left = buildTree(str, index);
node->right = buildTree(str, index);
return node;
}
// 前序遍历打印二叉树
void preOrder(TreeNode* root) {
if (root == NULL) {
printf("# ");
return;
}
printf("%c ", root->val);
preOrder(root->left);
preOrder(root->right);
}
int main() {
char str[] = "AB##C##";
int index = 0;
TreeNode* root = buildTree(str, &index);
preOrder(root); // 打印结果:A B # # C # #
return 0;
}
```
以上代码中,首先定义了二叉树结点的结构体,包括结点值以及左右子树指针。然后通过递归实现建树,当遇到 '#' 或者字符串结束符时返回 NULL,否则创建新结点,同时递归调用左右子树建立函数。最后通过前序遍历打印二叉树。
阅读全文