假设二叉树采用二叉链存储结构存储,设计一个算法SonNodes,求出一棵给定二叉树的所有非叶子结点的个数 已知二叉树结构体声明如下: typedef struct node{ ElemType data; struct node *lchild; struct node *rchild; } BTNode; 根据上述要求完成算法中的代码,并将完整代码写在答题框内(二叉树结构体声明无需写到答题框) int SonNodes(BTNode *b){ //补充算法中的代码 }
时间: 2024-03-17 11:46:38 浏览: 119
下面是算法SonNodes的代码实现:
```
int SonNodes(BTNode *b){
if(b == NULL || (b->lchild == NULL && b->rchild == NULL)){ //递归结束条件
return 0;
}
else{
return SonNodes(b->lchild) + SonNodes(b->rchild) + 1; //递归调用
}
}
```
算法思路:
1. 如果当前节点为空或者是叶子节点(即左右子树都为空),那么返回0,表示当前节点不是非叶子节点。
2. 如果当前节点不是叶子节点,那么就递归求解左子树和右子树的非叶子节点个数,并将它们的和加1,表示当前节点也是一个非叶子节点。
3. 最终返回的结果就是整棵二叉树的非叶子节点个数。
算法时间复杂度为O(n),其中n为二叉树的节点个数。
相关问题
假设二叉树采用二叉链存储结构存储,设计一个算法,输出一棵给定二叉树的所有叶子结点,给出C语言代码
以下是输出给定二叉树的所有叶子结点的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
/* 定义二叉树结构体 */
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* 创建二叉树 */
void CreateBiTree(BiTree *T) {
int data;
scanf("%d", &data);
if (data == -1) {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = data;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
/* 输出叶子结点 */
void PrintLeaf(BiTree T) {
if (T) {
if (!T->lchild && !T->rchild) { /* 如果是叶子结点 */
printf("%d ", T->data);
}
PrintLeaf(T->lchild);
PrintLeaf(T->rchild);
}
}
int main() {
BiTree T = NULL;
printf("请输入二叉树的前序遍历序列,-1表示空结点:\n");
CreateBiTree(&T);
printf("叶子结点为:");
PrintLeaf(T);
printf("\n");
return 0;
}
```
在该代码中,CreateBiTree函数用于创建二叉树,PrintLeaf函数用于输出二叉树的所有叶子结点。程序首先输入二叉树的前序遍历序列,然后输出二叉树的所有叶子结点。
假设二叉树采用二叉链存储结构存储,设计一个算法: 求一棵给定二叉树中的叶子结点个数。 计算二叉树的深度。
好的,针对您的问题,我分别回答:
1. 求一棵给定二叉树中的叶子结点个数的算法如下:
```
int countLeafNodes(TreeNode* root) {
if(root == NULL) {
return 0;
}
if(root->left == NULL && root->right == NULL) {
return 1;
}
return countLeafNodes(root->left) + countLeafNodes(root->right);
}
```
该算法通过递归遍历二叉树,对于每个节点,判断其左右子节点是否为空,如果两个子节点都为空,则该节点为叶子节点,返回1;否则,递归遍历该节点的左右子节点,并将两个子树的叶子节点数相加,即为该节点的叶子节点数。
2. 计算二叉树的深度的算法如下:
```
int maxDepth(TreeNode* root) {
if(root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
```
该算法同样采用递归的方式遍历二叉树,对于每个节点,计算其左右子树的深度,并取两者中的较大值,然后加1,即为该节点的深度。最终返回根节点的深度即可。