【PTA刷题+代码+详解】求二叉树度为1的结点个数(递归法)

2023-12-13 07:08:59

文章目录

    • 题目
    • C代码
    • 详解

题目

在二叉树T中,其度为1的结点是指某结点只有左孩子或只有右孩子。利用递归方法求二叉树T的度为1的结点个数。
1)如果T=NULL,则是空树,度为1的结点个数为0,返回值为0;
2)如果T->lchild=NULL或T->rchild=NULL(注意:左右孩子同时为NULL时,则是叶子结点,而不是度为1的结点),则是度为1的结点,返回值为1;
3)利用递归方法求其左右子树中的度为1的结点个数;并输出二叉树T的度为1的结点个数。

函数接口定义

在这里描述函数接口。例如:
int DegreeOne(BiTree T);

裁判测试程序样例

裁判测试程序样例如下:
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    char data;
    struct node *lchild;
    struct node *rchild;
}BiNode, *BiTree;

// 先序建立二叉树 (输入时,按先序次序输入二叉树中结点的值,以 # 字符表示空树)
BiTree createBiTree()
{
    BiTree T;
    char c;
    scanf("%c", &c);
    if (c == '#')
        T = NULL;
    else
    {
        T = (BiTree)malloc(sizeof(BiNode));
        T->data = c;
        T->lchild = createBiTree();//先序创建左子树
        T->rchild = createBiTree();//先序创建右子树
    }

    return T;
}

// 递归方法求二叉树中,度为1的结点个数
/* 请在这里填写答案 */

int main( ) {

    BiTree T = createBiTree(); // 建立二叉树
    printf("%d\n",DegreeOne(T));
    return 0;
}

输入样例1:

在这里给出一组输入。例如:

#

输出样例1:

在这里给出相应的输出。例如:

0

输入样例2:

在这里给出一组输入。例如:

ab###

输出样例2:

在这里给出相应的输出。例如:

1

输入样例3:

在这里给出一组输入。例如:

abc##de#g##f###

输出样例3:

在这里给出相应的输出。例如:

2

C代码

 int DegreeOne(BiTree T){
    if(T==NULL){
        return 0;
    }
    if(T->lchild != NULL &&T->rchild != NULL){//某结点有左右子树
        return DegreeOne(T->lchild)+DegreeOne(T->rchild);
    }
    else if(T->lchild != NULL && T->rchild == NULL){//某结点只有左子树
        return 1+DegreeOne(T->lchild);
    }
    else if(T->lchild == NULL && T->rchild != NULL){//某结点只有右子树
        return 1+DegreeOne(T->rchild);
    }
    return 0;
}

详解

这个问题要求使用递归方法求二叉树中度为1的结点个数。度为1的结点是指某结点只有左孩子或只有右孩子。

首先,让我们来看看提供的C代码:

int DegreeOne(BiTree T){
    if(T==NULL){
        return 0;
    }
    if(T->lchild != NULL && T->rchild != NULL){ // 某结点有左右子树
        return DegreeOne(T->lchild) + DegreeOne(T->rchild);
    }
    else if(T->lchild != NULL && T->rchild == NULL){ // 某结点只有左子树
        return 1 + DegreeOne(T->lchild);
    }
    else if(T->lchild == NULL && T->rchild != NULL){ // 某结点只有右子树
        return 1 + DegreeOne(T->rchild);
    }
    return 0;
}

现在让我们一步步解释这段代码:

  1. 递归终止条件:
  • 如果传入的二叉树结点 T 为 NULL,说明是空树,度为1的结点个数为0,返回值为0。
  1. 递归调用:
  • 如果某结点 T 有左右子树,说明这是一个度为2的结点,递归调用 DegreeOne 函数分别计算其左右子树中度为1的结点个数,并将它们相加。
  1. 度为1的结点情况:
  • 如果某结点 T 只有左子树而没有右子树,说明这是一个度为1的结点。递归调用 DegreeOne 函数计算其左子树中度为1的结点个数,并在结果上加1。

  • 如果某结点 T 只有右子树而没有左子树,同样说明这是一个度为1的结点。递归调用 DegreeOne 函数计算其右子树中度为1的结点个数,并在结果上加1。

  1. 返回结果:
  • 返回递归调用的结果,即度为1的结点个数。

现在我们来分析一下,以输入样例为例:

abc##de#g##f###

对应的二叉树结构如下:

image-20231213003222056

通过计算,可以得到度为1的结点个数为2。这是因为结点 e 和结点 f 是度为1的结点。函数 DegreeOne 在这个例子中应该返回 2。

文章来源:https://blog.csdn.net/weixin_75202470/article/details/134962081
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。