编写一个C程序,实现功能具体如下: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的结点个数; 7.统计二叉树的叶结点个数。
时间: 2023-11-14 09:26:26 浏览: 82
好的,以下是 C 语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
struct Node *left;
struct Node *right;
} Node;
Node* createNode(int val) {
Node* node = (Node*)malloc(sizeof(Node));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
Node* buildTree(int* vals, int len) {
if (len == 0) {
return NULL;
}
Node* root = createNode(vals[0]);
Node* queue[len];
int q_size = 0;
queue[q_size++] = root;
int i = 1;
while (q_size > 0 && i < len) {
Node* cur = queue[--q_size];
if (vals[i] != -1) {
cur->left = createNode(vals[i]);
queue[q_size++] = cur->left;
}
i++;
if (i >= len) {
break;
}
if (vals[i] != -1) {
cur->right = createNode(vals[i]);
queue[q_size++] = cur->right;
}
i++;
}
return root;
}
void inorderTraversal(Node* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left);
printf("%d ", node->val);
inorderTraversal(node->right);
}
void preorderTraversal(Node* node) {
if (node == NULL) {
return;
}
printf("%d ", node->val);
preorderTraversal(node->left);
preorderTraversal(node->right);
}
void postorderTraversal(Node* node) {
if (node == NULL) {
return;
}
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%d ", node->val);
}
int maxDepth(Node* node) {
if (node == NULL) {
return 0;
}
int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
int countNodes(Node* node) {
if (node == NULL) {
return 0;
}
return 1 + countNodes(node->left) + countNodes(node->right);
}
int countLeaves(Node* node) {
if (node == NULL) {
return 0;
}
if (node->left == NULL && node->right == NULL) {
return 1;
}
return countLeaves(node->left) + countLeaves(node->right);
}
int main() {
int vals[] = {1, 2, 3, -1, 4};
Node* root = buildTree(vals, 5);
inorderTraversal(root); printf("\n"); // 2 1 4 3
preorderTraversal(root); printf("\n"); // 1 2 3 4
postorderTraversal(root); printf("\n"); // 2 4 3 1
printf("%d\n", maxDepth(root)); // 3
printf("%d\n", countNodes(root)); // 4
printf("%d\n", countLeaves(root)); // 2
return 0;
}
```
以上代码实现了建立二叉树、中序遍历、前序遍历、后序遍历、计算深度、统计结点个数和统计叶结点个数等功能。其中,建立二叉树的函数 `buildTree` 接受一个整数数组和数组长度作为参数,这个数组是按照从上到下、从左到右的顺序存储二叉树节点的值,如果该节点为空,则用 `-1` 占位。例如,数组 `{1, 2, 3, -1, 4}` 表示以下二叉树:
```
1
/ \
2 3
/
4
```
如果你想要测试一下代码的功能,可以这样写:
```c
int vals[] = {1, 2, 3, -1, 4};
Node* root = buildTree(vals, 5);
inorderTraversal(root); printf("\n"); // 2 1 4 3
preorderTraversal(root); printf("\n"); // 1 2 3 4
postorderTraversal(root); printf("\n"); // 2 4 3 1
printf("%d\n", maxDepth(root)); // 3
printf("%d\n", countNodes(root)); // 4
printf("%d\n", countLeaves(root)); // 2
```
希望这个程序能够帮助到你!
阅读全文