用c语言 (1)构造利用二叉链表存储表示的二叉树; (2)利用先序遍历创建一个二叉树; (3)递归计算二叉树的深度和叶子结点的个数。
时间: 2024-01-23 11:44:34 浏览: 81
以下是用C语言实现的二叉树的构造、遍历和统计深度、叶子节点个数的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建一个新节点
struct TreeNode* createNode(int val) {
struct TreeNode* newNode = (struct TreeNode*) malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 构造二叉树
void constructTree(struct TreeNode** root) {
int val;
scanf("%d", &val);
if (val == -1) {
*root = NULL;
return;
}
*root = createNode(val);
constructTree(&((*root)->left));
constructTree(&((*root)->right));
}
// 先序遍历创建二叉树
struct TreeNode* createTree() {
struct TreeNode* root = NULL;
printf("请输入先序遍历序列(-1表示NULL):\n");
constructTree(&root);
return root;
}
// 计算深度
int getDepth(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}
// 计算叶子节点个数
int getNumOfLeaves(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return getNumOfLeaves(root->left) + getNumOfLeaves(root->right);
}
int main() {
struct TreeNode* root = createTree();
printf("二叉树的深度为:%d\n", getDepth(root));
printf("二叉树的叶子节点个数为:%d\n", getNumOfLeaves(root));
return 0;
}
```
其中,`createNode` 函数用于创建一个新节点,`constructTree` 函数用于构造二叉树(采用先序遍历,输入 `-1` 表示 `NULL`),`createTree` 函数用于调用 `constructTree` 创建二叉树,`getDepth` 函数用于计算二叉树的深度,`getNumOfLeaves` 函数用于计算二叉树的叶子节点个数。在主函数中,先调用 `createTree` 创建二叉树,然后调用 `getDepth` 和 `getNumOfLeaves` 分别计算二叉树的深度和叶子节点个数,并输出结果。
阅读全文