给出一个完整的从键盘输入的C语言代码(包含以下条件):按先序序列构造一棵二叉链表表示的二叉树T,对这棵二叉树进行中序遍历(递归算法),求二叉树的高度,求二叉树叶结点数目,将二叉树每个结点的左右子树交换位置。
时间: 2024-11-19 09:14:49 浏览: 34
下面是一个完整的C语言代码示例,它实现了上述需求:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 先序遍历(递归)
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val); // 先访问根节点
preorderTraversal(root->left); // 再遍历左子树
preorderTraversal(root->right); // 最后遍历右子树
}
}
// 中序遍历(递归)
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->val); // 先遍历左子树
inorderTraversal(root->right); // 再访问根节点和右子树
}
}
// 求高度(递归)
int heightOfTree(TreeNode* root) {
if (root == NULL)
return 0;
else {
int leftHeight = heightOfTree(root->left);
int rightHeight = heightOfTree(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
}
// 求叶节点数
int countLeaves(TreeNode* root) {
if (root == NULL || (root->left == NULL && root->right == NULL))
return 1;
else
return countLeaves(root->left) + countLeaves(root->right);
}
// 子树交换
void swapChildren(TreeNode* node) {
if (node != NULL) {
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
}
}
int main() {
// 输入先序序列
int input[100], n;
printf("请输入二叉树的先序遍历序列(以空格分隔): ");
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &input[i]);
}
// 构建二叉树
TreeNode* root = createNode(input[0]);
for (int i = 1; i < n; ++i) {
TreeNode* cur = root;
while (cur != NULL && input[i] != cur->val) {
if (input[i] < cur->val)
cur = cur->left;
else
cur = cur->right;
}
cur->left = createNode(input[i]);
}
// 打印中序遍历结果
printf("\n中序遍历结果: ");
inorderTraversal(root);
// 计算并打印高度
int treeHeight = heightOfTree(root);
printf("\n树的高度: %d\n", treeHeight);
// 计算叶节点数
int leafCount = countLeaves(root);
printf("叶节点数目: %d\n", leafCount);
// 打印交换后的子树
printf("\n交换子树前的树: \n");
preorderTraversal(root);
swapChildren(root);
printf("\n交换子树后的树: \n");
preorderTraversal(root);
return 0;
}
```
这个程序首先通过用户输入创建一棵二叉树,然后进行中序遍历、计算高度和叶节点数,并展示了交换子树前后的情况。注意,在实际运行时,您需要确保提供的先序序列长度足够用于构建完整二叉树。如果输入不满足二叉树的特性(如重复元素或非完全二叉树),则可能导致错误。
阅读全文