用c语言,使用链式存储二叉树,二叉树由用户从控制面板进行输入,输入后计算二叉树的叶子数目和深度
时间: 2024-11-18 10:15:17 浏览: 10
交互修改.rp
在C语言中,我们可以使用链式存储结构来实现二叉树,因为链表非常适合表示这种非线性的数据结构。首先,我们需要定义一个二叉树节点的数据结构,它通常包含两个指针,分别指向左孩子和右孩子。对于用户输入,可以设计一个循环,提示用户逐个输入节点值并创建新的节点。
下面是一个简单的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int val) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 插入节点到二叉树
void insert(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
} else if (val < (*root)->val) {
insert(&(*root)->left, val);
} else {
insert(&(*root)->right, val);
}
}
// 计算叶子数和深度
int countLeaves(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1; // 叶子节点
return countLeaves(root->left) + countLeaves(root->right);
}
int getDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + MAX(getDepth(root->left), getDepth(root->right)); // 递归计算最大深度
}
int main() {
TreeNode* root = NULL;
while (true) {
printf("请输入节点值(输入-1结束):");
int val = scanf("%d", &val);
if (val == -1) break;
insert(&root, val);
}
int leafCount = countLeaves(root);
int treeDepth = getDepth(root);
printf("二叉树的叶子数是:%d\n", leafCount);
printf("二叉树的最大深度是:%d\n", treeDepth);
return 0;
}
```
在这个程序中,我们首先通过`insert`函数将用户输入插入到二叉树中,然后使用`countLeaves`和`getDepth`函数计算叶节点数和树的深度。当用户输入-1时,程序停止接受输入并显示结果。
阅读全文