1-1 统计度为1的结点数

分数 3

作者黄龙军

单位绍兴文理学院

要求实现函数，统计并返回二叉树中的度为1的结点数。二叉树采用二叉链表存储，结点结构如下：

struct BiTNode {               // 结点结构
    char data;                 // 结点数据域
    BiTNode *lchild, *rchild;  // 左、右孩子指针
};

函数接口定义：

int CountSingle(BiTNode *T);

其中参数 T是指向二叉树根结点的指针。

裁判测试程序样例：

#include<iostream>
#include<string>
using namespace std;

struct BiTNode {
    char data;
    BiTNode *lchild, *rchild;
};

int CountSingle(BiTNode *T);         // 统计并返回度为1的结点数
BiTNode *CreateBiTree(string &s);  // 创建二叉树，s存放带虚结点的先序遍历序列

int main() {
    string s;
    while(cin>>s) {
        BiTNode* root=CreateBiTree(s);
        cout<<CountSingle(root)<<endl;
    }    
    return 0;
}

// 请在此处填写答案

// 按字符串s创建二叉树，返回根结点指针
BiTNode *CreateBiTree(string &s) {
    if(s[0]=='*') {
        s=s.substr(1);
        return NULL; 
    }
    BiTNode *p=new BiTNode;
    p->data=s[0];
    s=s.substr(1);
    p->lchild=CreateBiTree(s);
    p->rchild=CreateBiTree(s);
    return p;
}

输入样例：

HDA**C*B**GF*E***
-+a**xb**-c**d**/e**f**

输出样例：

3
0

解析

int CountSingle(BiTNode* T) {
    if (T == NULL) {
        return 0;
    }
    int current = 0;
    bool has_lchild = (T->lchild != NULL);
    bool has_rchild = (T->rchild != NULL);
    if (has_lchild != has_rchild) {
        current++;
    }
    return current + CountSingle(T->lchild) + CountSingle(T->rchild);
}

注意

思路

递归遍历二叉树：二叉树的结构具有递归性，因此可以采用递归的方式遍历每个节点。
判断节点的度

：对于每个节点，检查其左子节点和右子节点的存在情况：
- 如果左子节点存在而右子节点不存在，或者左子节点不存在而右子节点存在，则该节点的度为 1。
- 否则，该节点的度不为 1（可能为 0 或 2）。
累加度为 1 的节点数：对每个节点进行度的判断后，累加当前节点的贡献（1 如果度为 1，否则为 0），再加上其左子树和右子树中度为 1 的节点数，即可得到总的度为 1 的节点数。

解释

递归终止条件：当节点为nullptr（空节点）时，返回 0，因为空节点没有子节点，不贡献度为 1 的节点。
节点度的判断：通过检查左子节点（lchild）和右子节点（rchild）是否存在，若仅有一个存在，则当前节点度为 1，贡献 1；否则贡献 0。
递归累加：对当前节点的贡献值加上其左子树和右子树中度为 1 的节点数，得到最终结果。

这种方法利用二叉树的递归特性，遍历每个节点一次，时间复杂度为 O (n)，其中 n 为二叉树的节点总数，空间复杂度为 O (h)（h 为二叉树的高度），主要用于递归调用栈的开销。

1-2 二叉树求结点数

分数 3

作者鲁法明

单位山东科技大学

编写函数计算二叉树中的节点个数。二叉树采用二叉链表存储结构。

函数接口定义：

int NodeCountOfBiTree ( BiTree T);

其中 T是二叉树根节点的地址。

裁判测试程序样例：

//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>

//函数状态码定义
#define TRUE       1
#define FALSE      0
#define OK         1
#define ERROR      0
#define OVERFLOW   -1
#define INFEASIBLE -2

typedef int Status;

//二叉链表存储结构定义
typedef int TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;

//创建二叉树各结点，输入0代表创建空树。
//采用递归的思想创建
//递归边界：空树如何创建呢：直接输入0；
//递归关系：非空树的创建问题，可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树。左右子树递归即可完成创建！
Status CreateBiTree(BiTree &T){
   TElemType e;
   scanf("%d",&e);
   if(e==0)T=NULL;
   else{
     T=(BiTree)malloc(sizeof(BiTNode));
     if(!T)exit(OVERFLOW);
     T->data=e;
     CreateBiTree(T->lchild);
     CreateBiTree(T->rchild);
   }
   return OK;  
}

//下面是需要实现的函数的声明
int NodeCountOfBiTree ( BiTree T);
//下面是主函数
int main()
{
   BiTree T;
   int n;     
   CreateBiTree(T);  //先序递归创建二叉树     
   n= NodeCountOfBiTree(T);     
   printf("%d",n);
     return 0;
}

/* 请在这里填写答案 */

输入样例（注意输入0代表空子树）：

1 3 0 0 5 3 0 0 0

输出样例：

解析

int NodeCountOfBiTree(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    return 1 + NodeCountOfBiTree(T->lchild) + NodeCountOfBiTree(T->rchild);
}

注意

要确定二叉树中的节点个数，核心是统计所有非空节点的数量（虚节点，如之前例子中的*，不视为有效节点）。

逻辑计算：递归遍历统计

二叉树的节点个数可以通过递归遍历计算，思路是：当前树的节点数 = 1（当前根节点） + 左子树的节点数 + 右子树的节点数

1-3 求二叉树的高度

分数 5

作者 YJ

单位西南石油大学

输入二叉树的先序序列以创建二叉树，并求出该二叉树的高度。

函数接口定义：

int Depth(BiTree Tree);

其中 Tree 是用户传入的参数，代表指向二叉树根节点的指针。

裁判测试程序样例：

#include<stdio.h>
#include<malloc.h>
#define len sizeof(struct BiTNode )

typedef struct BiTNode
{
    char data;  //数据域
    struct BiTNode *lchild;  //左孩子指针
    struct BiTNode *rchild;  //右孩子指针
}BiTNode,*BiTree;

 void creat(BiTree &Tree)//构建二叉树
{
  char ch;
  scanf("%c",&ch);  //输入数据值
  if(ch=='#')  //输入#时结束二叉树的构建
    Tree=NULL;
  else
  {
      Tree=(BiTree)malloc(sizeof(BiTNode));
      Tree->data=ch;
      creat(Tree->lchild);  //递归创建左子树
      creat(Tree->rchild);  //递归创建右子树
  }
}
int Depth(BiTree Tree);//求出二叉树的高度
int main()
{
    BiTree Tree;
    creat(Tree);//创建二叉树
    printf("%d\n",Depth(Tree));//打印高度
    return 0;
}

/* 请在这里填写答案 */

输入样例：

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

AB##CD##EF###

输出样例：

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

解析

int Depth(BiTree Tree) {
    if (Tree == NULL) {
        return 0;
    }
    int leftDepth = Depth(Tree->lchild);
    int rightDepth = Depth(Tree->rchild);
    if (leftDepth > rightDepth) {
        return 1 + leftDepth;
    }
    else
    {
        return 1 + rightDepth;
    }
}