用C语言写1. 实验采用二叉链表作为二叉树的存储结构, 2. 完成对二叉树的建立、先序、中序、后序; 3. 完成按层次遍历的操作; 4. 求所有叶子及结点总数的操作; 5. 编写主程序实现对这些运算的测试。
时间: 2023-06-11 17:08:39 浏览: 80
下面是用C语言实现以上要求的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
} else {
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = val;
root->left = createTree();
root->right = createTree();
return root;
}
}
// 先序遍历
void preOrder(TreeNode *root) {
if (root) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
// 中序遍历
void inOrder(TreeNode *root) {
if (root) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
// 后序遍历
void postOrder(TreeNode *root) {
if (root) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
// 按层次遍历
void levelOrder(TreeNode *root) {
TreeNode *queue[1000]; // 定义队列
int front = -1, rear = -1;
if (root) {
queue[++rear] = root;
}
while (front != rear) {
TreeNode *node = queue[++front];
printf("%d ", node->data);
if (node->left) {
queue[++rear] = node->left;
}
if (node->right) {
queue[++rear] = node->right;
}
}
}
// 求叶子结点数和总结点数
void countNodes(TreeNode *root, int *leafCount, int *nodeCount) {
if (root) {
(*nodeCount)++;
if (!root->left && !root->right) {
(*leafCount)++;
}
countNodes(root->left, leafCount, nodeCount);
countNodes(root->right, leafCount, nodeCount);
}
}
int main() {
TreeNode *root = createTree();
printf("先序遍历:");
preOrder(root);
printf("\n中序遍历:");
inOrder(root);
printf("\n后序遍历:");
postOrder(root);
printf("\n按层次遍历:");
levelOrder(root);
int leafCount = 0, nodeCount = 0;
countNodes(root, &leafCount, &nodeCount);
printf("\n叶子结点数:%d,总结点数:%d\n", leafCount, nodeCount);
return 0;
}
```
输入样例:
```
1 2 -1 -1 3 4 -1 -1 5 -1 -1
```
输出样例:
```
先序遍历:1 2 3 4 5
中序遍历:2 1 4 3 5
后序遍历:2 4 5 3 1
按层次遍历:1 2 3 4 5
叶子结点数:2,总结点数:5
```
阅读全文