完成二叉树的算法,补充完整,菜单如下: printf("\n 1. 建立二叉树方法1 "); printf("\n 2. 建立二叉树方法2"); printf("\n 3. 中序递归遍历二叉树"); printf("\n 4. 计算树中结点个数"); printf("\n 5. 先序递归遍历二叉树"); printf("\n 6. 后序递归遍历二叉树"); printf("\n 7. 结束程序运行");
时间: 2023-07-13 14:13:19 浏览: 93
这里提供一个简单的二叉树结构体,以及对应的菜单实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 建立二叉树方法1
TreeNode* createTree1() {
int data;
printf("请按照前序遍历的顺序输入二叉树中各节点的值(-1表示空节点):\n");
scanf("%d", &data);
if (data == -1) {
return NULL;
}
TreeNode* node = createNode(data);
node->left = createTree1();
node->right = createTree1();
return node;
}
// 建立二叉树方法2
TreeNode* createTree2() {
int data;
printf("请按照层次遍历的顺序输入二叉树中各节点的值(-1表示空节点):\n");
scanf("%d", &data);
if (data == -1) {
return NULL;
}
TreeNode* root = createNode(data);
TreeNode* queue[100]; // 用队列存储每层的节点
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
TreeNode* node = queue[front++];
printf("请输入%d的左子节点:", node->data);
scanf("%d", &data);
if (data != -1) {
node->left = createNode(data);
queue[rear++] = node->left;
}
printf("请输入%d的右子节点:", node->data);
scanf("%d", &data);
if (data != -1) {
node->right = createNode(data);
queue[rear++] = node->right;
}
}
return root;
}
// 中序递归遍历二叉树
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
// 计算树中结点个数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
// 先序递归遍历二叉树
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 后序递归遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
// 主函数
int main() {
int choice;
TreeNode* root = NULL;
do {
printf("\n请选择菜单:\n");
printf("1. 建立二叉树方法1\n");
printf("2. 建立二叉树方法2\n");
printf("3. 中序递归遍历二叉树\n");
printf("4. 计算树中结点个数\n");
printf("5. 先序递归遍历二叉树\n");
printf("6. 后序递归遍历二叉树\n");
printf("7. 结束程序运行\n");
scanf("%d", &choice);
switch (choice) {
case 1:
root = createTree1();
break;
case 2:
root = createTree2();
break;
case 3:
printf("中序遍历结果:");
inorderTraversal(root);
printf("\n");
break;
case 4:
printf("节点个数:%d\n", countNodes(root));
break;
case 5:
printf("先序遍历结果:");
preorderTraversal(root);
printf("\n");
break;
case 6:
printf("后序遍历结果:");
postorderTraversal(root);
printf("\n");
break;
case 7:
printf("程序已结束!\n");
break;
default:
printf("输入有误,请重新输入!\n");
break;
}
} while (choice != 7);
return 0;
}
```
其中,方法1和方法2分别实现了前序遍历和层次遍历建立二叉树的功能。中序、先序和后序遍历采用递归实现,计算节点个数也采用递归实现。
阅读全文
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)