C语言假设二叉树的结点值是字符,根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。
时间: 2024-01-23 16:10:07 浏览: 85
数据结构 C语言建立二叉树
4星 · 用户满意度95%
好的,这是一个比较经典的二叉树建立问题。
假设输入的完整先序遍历序列为preorder,建立二叉树的过程可以用递归来实现。具体步骤如下:
1. 如果preorder为空,则返回空指针。
2. 否则,取出preorder的第一个元素作为根节点,并创建一个新的二叉树结点。
3. 将preorder分为左子树和右子树两部分,其中左子树包含所有比根节点小的元素,右子树包含所有比根节点大的元素。
4. 递归建立左子树和右子树,并将它们分别挂到根节点的左右孩子上。
C语言代码如下:
```c
#include <stdlib.h>
#include <string.h>
// 二叉树结点定义
typedef struct TreeNode {
char val; // 结点值
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
// 递归建立二叉树
TreeNode* buildTree(char* preorder, int len) {
if (len == 0) {
return NULL;
}
// 创建根节点
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
root->left = NULL;
root->right = NULL;
// 分割左右子树
int i = 1;
while (i < len && preorder[i] < root->val) {
i++;
}
// 递归建立左右子树
root->left = buildTree(preorder + 1, i - 1);
root->right = buildTree(preorder + i, len - i);
return root;
}
// 测试代码
int main() {
char preorder[] = "ABDECF";
TreeNode* root = buildTree(preorder, strlen(preorder));
return 0;
}
```
以上代码只是一个简单的示例,实际应用中需要注意空指针和内存管理等问题。
阅读全文