用数据结构c语言编程,构造二叉链表存储二叉树T,三种方式递归遍历T,递归计算T的深度,递归统计T中结点的个数,递归统计T中叶子结点的个数的具体算法
时间: 2023-06-03 18:05:30 浏览: 104
非常感谢您的提问!这是一个关于数据结构和算法的问题。我很乐意帮助您回答这个问题。
首先,让我们来了解一下二叉树和二叉链表的概念。
二叉树是一种树形结构,它的每个节点最多有两个子节点。
二叉链表是一种利用链式存储结构表示二叉树的方法,它的每个节点包括三个字段,分别是数据域、指向左子树的指针和指向右子树的指针。
构造二叉链表存储二叉树T的算法如下:
```c
typedef struct TreeNode *BiTree;
struct TreeNode {
int val;
BiTree left;
BiTree right;
};
BiTree createTree(void) {
int val;
scanf("%d", &val);
if (val == 0) {
return NULL; // 0 表示空节点
}
BiTree T = (BiTree) malloc(sizeof(struct TreeNode));
T->val = val;
T->left = createTree();
T->right = createTree();
return T;
}
```
其中,`createTree()` 函数会从标准输入中逐层递归读入每个节点的值,直至遇到0,表示递归结束。此时,该节点的值为空,并且其指针域均为空。
接下来,让我们来看看如何递归遍历T、计算T的深度、统计T中结点的个数以及统计T中叶子结点的个数。
先来看中序遍历、前序遍历和后序遍历的算法:
```c
// 中序遍历
void inorder(BiTree T) {
if (!T) {
return;
}
inorder(T->left);
printf("%d ", T->val);
inorder(T->right);
}
// 前序遍历
void preorder(BiTree T) {
if (!T) {
return;
}
printf("%d ", T->val);
preorder(T->left);
preorder(T->right);
}
// 后序遍历
void postorder(BiTree T) {
if (!T) {
return;
}
postorder(T->left);
postorder(T->right);
printf("%d ", T->val);
}
```
以上三个函数分别实现了中序遍历、前序遍历和后序遍历的递归算法。其中,`T` 表示当前子树的根节点。
计算T的深度的算法如下:
```c
int depth(BiTree T) {
if (!T) {
return 0;
}
int left_depth = depth(T->left);
int right_depth = depth(T->right);
return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}
```
统计T中结点的个数的算法如下:
```c
int countNodes(BiTree T) {
if (!T) {
return 0;
}
return countNodes(T->left) + countNodes(T->right) + 1;
}
```
统计T中叶子结点的个数的算法如下:
```c
int countLeaves(BiTree T) {
if (!T) {
return 0;
}
if (!T->left && !T->right) {
return 1;
}
return countLeaves(T->left) + countLeaves(T->right);
}
```
以上四个函数分别实现了递归遍历T、计算T的深度、统计T中结点的个数以及统计T中叶子结点的个数的算法。
希望以上回答对您有帮助。如果您有其他问题,欢迎继续提问。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231045021.png)
![-](https://img-home.csdnimg.cn/images/20241231044955.png)
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)