用c语言编写以下程序:建立一颗二叉树(以链表存储),对该二叉树进行遍历并输出该二叉树的前序、中序、后序遍历序列(三中遍历任选一种采用非递归算法),实现二叉树左右子树的交换,统计二叉树中叶子节点个数,且此代码是手动输入数据。
时间: 2024-12-06 11:11:34 浏览: 39
建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数
在C语言中,我们可以创建一个二叉树结构,并使用非递归的方式实现前序、中序和后序遍历。以下是简单的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode != NULL) {
newNode->data = value;
newNode->left = newNode->right = NULL;
}
return newNode;
}
// 插入节点到二叉树
void insert(TreeNode** root, int value) {
if (*root == NULL) {
*root = createNode(value);
} else if (value < (*root)->data) {
insert(&((*root)->left), value);
} else {
insert(&((*root)->right), value);
}
}
// 非递归前序遍历
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data); // 先访问根
preorderTraversal(root->left); // 再访问左子树
preorderTraversal(root->right); // 最后访问右子树
}
}
// 非递归中序遍历
void inorderTraversal(TreeNode* root) {
if (root != NULL) {
inorderTraversal(root->left); // 先访问左子树
printf("%d ", root->data); // 再访问根
inorderTraversal(root->right); // 最后访问右子树
}
}
// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
if (root != NULL) {
postorderTraversal(root->left); // 先访问左子树
postorderTraversal(root->right); // 再访问右子树
printf("%d ", root->data); // 最后访问根
}
}
// 交换左右子树
void swapChildren(TreeNode** node) {
if (*node != NULL) {
TreeNode* temp = (*node)->left;
(*node)->left = (*node)->right;
(*node)->right = temp;
}
}
// 统计叶子节点
int countLeaves(TreeNode* root) {
if (root == NULL)
return 0;
else if (root->left == NULL && root->right == NULL)
return 1;
else
return countLeaves(root->left) + countLeaves(root->right);
}
int main() {
int n, value;
printf("Enter number of nodes to insert: ");
scanf("%d", &n);
TreeNode* root = NULL;
for (int i = 0; i < n; ++i) {
printf("Enter node %d: ", i+1);
scanf("%d", &value);
insert(&root, value);
}
printf("\nPreorder Traversal: ");
preorderTraversal(root);
printf("\nInorder Traversal: ");
inorderTraversal(root);
printf("\nPostorder Traversal: ");
postorderTraversal(root);
TreeNode* temp = root;
printf("\nAfter swapping children: ");
while (temp != NULL) {
printf("%d ", temp->data);
swapChildren(&temp);
}
printf("\nNumber of leaf nodes: %d\n", countLeaves(root));
return 0;
}
```
运行这个程序,用户可以手动输入构建二叉树的数据,然后依次查看不同的遍历结果以及叶节点的数量。注意,上述代码假定输入的是整数值。
阅读全文