用c语言创建二叉树,已知先序输出ABDECFG,求中序和后序遍历输出,并求该二叉树的结点个数
时间: 2024-10-25 10:07:09 浏览: 29
在C语言中,我们可以使用结构体来表示二叉树节点,并通过递归的方式来进行遍历。给定先序遍历的结果 "ABDECFG",可以推断出根节点是 'A',然后根据先序遍历的特点(根-左-右),我们得知节点顺序。构建这样的二叉树后,再分别进行中序遍历和后序遍历。
首先,我们需要定义二叉树节点结构:
```c
typedef struct TreeNode {
char val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
接下来,根据先序遍历构造二叉树:
```c
TreeNode* createTree(char* preorder) {
if (preorder[0] == '\0') return NULL; // 空字符串表示空树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
int i = 1;
while (preorder[i]) { // 找到第一个非空字符作为当前节点的右子节点
TreeNode* current = root;
while (current->right && preorder[i] != current->right->val) {
current = current->right;
}
current->right = (preorder[i++] != '\0') ? (TreeNode*)malloc(sizeof(TreeNode)) : NULL; // 如果找到右子节点,分配空间并设置值
current->right->val = preorder[i++];
}
return root;
}
```
现在我们有了二叉树,可以进行中序和后序遍历:
```c
void inorderTraversal(TreeNode* node, char* traversal) {
if (node) {
inorderTraversal(node->left, traversal);
traversal += sprintf(traversal, "%c", node->val); // 中序:左-根-右
inorderTraversal(node->right, traversal);
}
}
void postorderTraversal(TreeNode* node, char* traversal) {
if (node) {
postorderTraversal(node->left, traversal);
postorderTraversal(node->right, traversal);
traversal += sprintf(traversal, "%c", node->val); // 后序:左-右-根
}
}
```
最后,计算节点个数:
```c
int countNodes(TreeNode* node) {
if (!node) return 0;
return 1 + countNodes(node->left) + countNodes(node->right);
}
```
对于给出的先序遍历 "ABDECFG",你可以使用上述函数创建二叉树,然后分别调用 `inorderTraversal` 和 `postorderTraversal` 函数获取中序和后序遍历结果,同时调用 `countNodes` 来得到节点总数。
阅读全文