用C语言实现,完成二叉树二叉链表结构的定义,实现二叉链表创建二叉树(尝试用递归算法实现),并实现先序、中序和后序遍历算法,实现二叉树求结点个数,求树的高度,求叶子结点数、交换二叉树左右子树的算法,并给出主函数,主函数中要包含通过switch语句创建菜单调用这几个算法的函数
时间: 2023-06-06 17:06:41 浏览: 65
好的,我理解了您的要求。以下是根据您提供的要求,实现的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体定义
typedef struct BiTreeNode {
int data;
struct BiTreeNode *lchild, *rchild;
} BiTreeNode, *BiTree;
// 创建二叉树
BiTree createBiTree() {
int data;
scanf("%d", &data);
if (data == -1) { // -1 表示该节点为空
return NULL;
}
BiTreeNode *node = (BiTreeNode *)malloc(sizeof(BiTreeNode));
node->data = data;
node->lchild = createBiTree();
node->rchild = createBiTree();
return node;
}
// 先序遍历
void preOrder(BiTree tree) {
if (tree == NULL) {
return;
}
printf("%d ", tree->data);
preOrder(tree->lchild);
preOrder(tree->rchild);
}
// 中序遍历
void inOrder(BiTree tree) {
if (tree == NULL) {
return;
}
inOrder(tree->lchild);
printf("%d ", tree->data);
inOrder(tree->rchild);
}
// 后序遍历
void postOrder(BiTree tree) {
if (tree == NULL) {
return;
}
postOrder(tree->lchild);
postOrder(tree->rchild);
printf("%d ", tree->data);
}
// 求结点个数
int countNodes(BiTree tree) {
if (tree == NULL) {
return 0;
}
return countNodes(tree->lchild) + countNodes(tree->rchild) + 1;
}
// 求树的高度
int getHeight(BiTree tree) {
if (tree == NULL) {
return 0;
}
int leftHeight = getHeight(tree->lchild);
int rightHeight = getHeight(tree->rchild);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 求叶子结点数
int countLeaves(BiTree tree) {
if (tree == NULL) {
return 0;
}
if (tree->lchild == NULL && tree->rchild == NULL) {
return 1;
}
return countLeaves(tree->lchild) + countLeaves(tree->rchild);
}
// 交换二叉树左右子树
void swapChildren(BiTree tree) {
if (tree == NULL) {
return;
}
BiTreeNode *temp = tree->lchild;
tree->lchild = tree->rchild;
tree->rchild = temp;
swapChildren(tree->lchild);
swapChildren(tree->rchild);
}
// 主函数
int main() {
BiTree tree = NULL;
printf("请输入二叉树的数据:\n");
tree = createBiTree();
while (1) {
int choice;
printf("\n请选择要执行的操作:\n");
printf("1. 先序遍历\n");
printf("2. 中序遍历\n");
printf("3. 后序遍历\n");
printf("4. 求结点个数\n");
printf("5. 求树的高度\n");
printf("6. 求叶子结点数\n");
printf("7. 交换左右子树\n");
printf("8. 退出程序\n");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("先序遍历结果:");
preOrder(tree);
break;
case 2:
printf("中序遍历结果:");
inOrder(tree);
break;
case 3:
printf("后序遍历结果:");
postOrder(tree);
break;
case 4:
printf("结点个数为:%d", countNodes(tree));
break;
case 5:
printf("树的高度为:%d", getHeight(tree));
break;
case 6:
printf("叶子结点个数为:%d", countLeaves(tree));
break;
case 7:
swapChildren(tree);
printf("交换左右子树成功!");
break;
case 8:
printf("程序已退出!\n");
return 0;
default:
printf("输入的操作选择不正确,请重新输入!\n");
}
}
return 0;
}
```
注意:由于我是机器人,无法运行 C 语言代码进行测试,所以以上代码可能存在语法错误或逻辑问题,建议您在使用前自行进行调试和测试。如有问题,可随时向我提问。