数据结构c语言 实验编写一个程序,实现二叉树的各种运算,并在此基础上设计一个主程序完成如下功能: 1)建立图6-6所示二叉树T. 2)输出二叉树T的深度。 3)输出二叉树T的叶子结点数。
时间: 2024-12-02 18:13:54 浏览: 39
2014-2015年西安电子科技大学902数据结构与C语言程序设计考研真题
5星 · 资源好评率100%
在C语言中,我们可以使用递归的方式来实现二叉树的基本操作,如构建、遍历以及计算深度和叶子节点数。首先,我们需要定义一个二叉树节点的数据结构:
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
接下来,我们编写函数分别实现以下功能:
1. **创建二叉树** (例如,图6-6所示的二叉树T):
- 根据给定的值和子节点列表来构建二叉树
2. **计算深度**:
- 使用递归的层次遍历方法计算二叉树的深度
3. **计算叶子节点**:
- 判断节点是否为叶子节点(即无左孩子也无右孩子的节点)
下面是一个简单的示例实现:
```c
// 创建节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
if (node) {
node->val = val;
node->left = NULL;
node->right = NULL;
}
return node;
}
// 插入节点到二叉树
void insertIntoTree(TreeNode** root, int val) {
if (*root == NULL) {
*root = createNode(val);
} else {
if (val < (*root)->val) {
insertIntoTree(&(*root)->left, val);
} else {
insertIntoTree(&(*root)->right, val);
}
}
}
// 计算深度
int treeDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + max(treeDepth(root->left), treeDepth(root->right));
}
// 判断是否为叶子节点
int isLeaf(TreeNode* node) {
return (node->left == NULL && node->right == NULL);
}
// 统计叶子节点数量
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
return isLeaf(root) ? 1 : countLeaves(root->left) + countLeaves(root->right);
}
int main() {
// 假设已经有一组数据来构建二叉树 T
// 构建二叉树
TreeNode* tRoot = NULL; // 二叉树根节点
insertIntoTree(&tRoot, ...); // 用实际数据替换 ...
// 输出深度
printf("Tree depth: %d\n", treeDepth(tRoot));
// 输出叶子节点数
printf("Number of leaves: %d\n", countLeaves(tRoot));
return 0;
}
```
记得用具体的数值替换`...`部分,然后运行这个程序即可得到所需的结果。如果你需要完整的源码,我可以帮你编写这部分代码。
阅读全文