用C语言实现1、按照先序遍历的顺序创建一个二叉链表; 2、对已建立的二叉树实现先序遍历、中序遍历、后序遍历、求深度、求结点数量等操作。 3、最好用菜单形式对应各个操作,使其编程一个完整的小软件。
时间: 2024-12-23 08:22:07 浏览: 4
二叉树的创建与遍历C语言实现代码.zip
在C语言中,我们通常使用结构体定义二叉树节点,并利用指针链接相邻节点来构建二叉链表。以下是先序遍历(根-左-右)创建二叉链表的基本步骤:
1. 定义二叉树节点结构:
```c
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
2. 创建新节点并插入到链表中(先序遍历):
```c
void insertPreorder(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = value;
if (!root) {
root = newNode;
} else {
insertNodePreorder(root, newNode);
}
}
void insertNodePreorder(TreeNode* node, TreeNode* newNode) {
if (node->left == NULL) {
node->left = newNode;
} else {
insertNodePreorder(node->left, newNode);
}
}
```
对于其他操作,例如遍历和计算树的相关属性:
3. 先序遍历:
```c
void preorderTraversal(TreeNode* node) {
if (node != NULL) {
printf("%d ", node->data); // 打印节点值
preorderTraversal(node->left);
preorderTraversal(node->right);
}
}
// 中序遍历和后序遍历类似,只是访问左右子节点的顺序不同
void inorderTraversal(TreeNode* node) { ... }
void postorderTraversal(TreeNode* node) { ... }
```
4. 求深度和结点数量:
```c
int depth(TreeNode* node) {
if (node == NULL)
return 0;
else
return 1 + max(depth(node->left), depth(node->right));
}
int countNodes(TreeNode* node) {
if (node == NULL)
return 0;
else
return 1 + countNodes(node->left) + countNodes(node->right);
}
```
为了创建一个完整的菜单驱动小软件,你可以使用`main()`函数配合循环和条件判断来设计菜单。这里仅提供基础框架:
```c
int main() {
TreeNode* root = NULL;
while (true) {
printf("请选择操作:\n");
printf("1. 创建树\n");
printf("2. 先序遍历\n");
printf("3. 中序遍历\n");
printf("4. 后序遍历\n");
printf("5. 深度\n");
printf("6. 节点数\n");
printf("7. 退出\n");
int choice;
scanf("%d", &choice);
switch (choice) {
case 1: insertPreorder(yourInput); break;
case 2: preorderTraversal(root); break;
// 其他case...此处省略
case 7: exit(0);
default: printf("无效选择,请重新输入。\n");
}
}
return 0;
}
```
阅读全文