1.通过键盘输入的扩充二叉树的层次遍历序列, 建立二叉树(如:序列:2,5,6,0,0,10,11,0,0,0,0 )。(设二叉树结点的数据为int型,其中扩充结点用’0’号表示)。然后按中序和后序输出此二叉树,求该树的叶结点个数和度数为2的结点个数)。用C语言写代码实现
时间: 2025-01-05 12:42:47 浏览: 12
首先,我们需要理解题目的要求:输入一个扩充二叉树的层次遍历序列,构建出对应的二叉树,然后进行中序遍历、后序遍历,并计算叶结点和度数为2的结点的数量。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点并插入到已有的二叉树
TreeNode* createNode(int val, TreeNode* root) {
if (val == 0)
return NULL;
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = newNode->right = NULL;
if (root == NULL)
return newNode;
else if (val < root->val)
root->left = createNode(val, root->left);
else
root->right = createNode(val, root->right);
return root;
}
// 层次遍历构建二叉树
TreeNode* buildTree(char* input, int start, int end) {
if (start > end)
return NULL;
int mid = start + (end - start) / 2;
TreeNode* root = createNode(input[mid] - '0', NULL);
root->left = buildTree(input, start, mid - 1);
root->right = buildTree(input, mid + 1, end);
return root;
}
// 中序遍历打印二叉树
void inorderTraversal(TreeNode* root, void(*print)(int)) {
if (root != NULL) {
inorderTraversal(root->left, print);
print(root->val);
inorderTraversal(root->right, print);
}
}
// 后序遍历打印二叉树
void postorderTraversal(TreeNode* root, void(*print)(int)) {
if (root != NULL) {
postorderTraversal(root->left, print);
postorderTraversal(root->right, print);
print(root->val);
}
}
// 计算叶结点和度为2的结点数量
int countLeavesAndDegreeTwo(TreeNode* root) {
int leaves = 0, degreeTwo = 0;
if (root == NULL)
return leaves, degreeTwo;
if (root->left == NULL && root->right == NULL) // 叶子节点
leaves++;
else if (root->left != NULL && root->right != NULL) // 度为2的节点
degreeTwo++;
degreeTwo += countLeavesAndDegreeTwo(root->left);
degreeTwo += countLeavesAndDegreeTwo(root->right);
return leaves, degreeTwo;
}
int main() {
char input[] = "2,5,6,0,0,10,11,0,0,0,0"; // 输入的层次遍历序列
int n = strlen(input);
TreeNode* root = buildTree(input, 0, n - 1);
printf("中序遍历: ");
inorderTraversal(root, printf); printf("\n");
printf("后序遍历: ");
postorderTraversal(root, printf); printf("\n");
int leaves, degreeTwo;
leaves = degreeTwo = countLeavesAndDegreeTwo(root);
printf("叶结点个数: %d\n", leaves);
printf("度数为2的结点个数: %d\n", degreeTwo);
return 0;
}
```
这段C代码实现了题目所要求的功能,包括构建二叉树、中序遍历、后序遍历以及计算叶节点和度为2的节点数量。运行这个程序时,你需要将层次遍历序列作为字符串传递给它。
阅读全文