以二叉链表作为二叉树的存储结构,请使用 C 语言分别实现以下递归算法: (1)将二叉树中所有结点的左右子树相互交换。 (2)求二叉树中叶子结点数目。 typedef char elemtype ; typedef struct node ( elemtype data ; struct node * Ichild ,* rchild ;} bittree ;//二叉链表 请使用以上二叉链表定义完成如下函数定义 bittree * swap ( bittree * root );// root指向二叉树的根结点 int leafnum ( bittree * root );//返回叶子结点数目
时间: 2024-03-06 10:47:35 浏览: 14
好的,以下是对应的递归算法实现:
1. 将二叉树中所有结点的左右子树相互交换
```
bittree* swap(bittree* root) {
if (root == NULL) {
return NULL;
}
bittree* temp = root->lchild;
root->lchild = swap(root->rchild);
root->rchild = swap(temp);
return root;
}
```
2. 求二叉树中叶子结点数目
```
int leafnum(bittree* root) {
if (root == NULL) {
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) {
return 1;
}
return leafnum(root->lchild) + leafnum(root->rchild);
}
```
相关问题
以二叉链表作为二叉树的存储结构。编写递归算法,计算二叉树中叶子结点的数目。请将下面的代码补充完整。
好的,以下是递归算法计算二叉树中叶子结点数目的C语言程序,以二叉链表作为二叉树的存储结构:
```
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点定义
typedef struct TreeNode {
int data;
struct TreeNode *lchild, *rchild;
} TreeNode;
// 创建二叉树
TreeNode* create_tree() {
int data;
scanf("%d", &data);
if (data == -1) { // 输入-1表示该节点为空
return NULL;
}
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->lchild = create_tree();
node->rchild = create_tree();
return node;
}
// 计算二叉树中叶子结点数目的递归算法
int count_leaf(TreeNode *root) {
if (root == NULL) { // 如果节点为空,则返回0
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) { // 如果节点为叶子结点,则返回1
return 1;
}
return count_leaf(root->lchild) + count_leaf(root->rchild); // 递归计算左子树和右子树的叶子结点数目之和
}
int main() {
printf("请输入二叉树的节点数据(-1表示该节点为空):\n");
TreeNode *root = create_tree();
printf("二叉树中叶子结点数目为:%d\n", count_leaf(root));
return 0;
}
```
在递归算法`count_leaf()`中,如果节点为空,则返回0;如果节点为叶子结点,则返回1;否则递归计算左子树和右子树的叶子结点数目之和。在`main()`函数中,首先调用`create_tree()`函数创建二叉树,然后调用`count_leaf()`函数计算二叉树中叶子结点数目。
以二叉链表作为二叉树的存储结构,编写以下算法: 统计二叉树的叶结点个数的编码、
以下是统计二叉树叶结点个数的算法的Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def count_leaf_nodes(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
# 测试代码
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print(count_leaf_nodes(root)) # 输出 4
```
该算法的思路是,如果当前节点是空节点,那么返回0;如果当前节点是叶子节点(即左右子节点都为空),那么返回1;否则递归计算左右子树的叶子节点数量之和。时间复杂度为 $O(n)$,其中 $n$ 是二叉树的节点数。