1-4 二叉树求深度和叶子数

分数 3

作者 鲁法明

单位 浙江大学

编写函数计算二叉树的深度以及叶子节点数。二叉树采用二叉链表存储结构

函数接口定义：

int GetDepthOfBiTree ( BiTree T);
int LeafCount(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
#define NULL  0
typedef int Status;

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

//创建二叉树各结点，输入零代表创建空树
//采用递归的思想创建
//递归边界：空树如何创建呢：直接输入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 GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);
//下面是主函数
int main()
{
   BiTree T;
   int depth, numberOfLeaves;
   CreateBiTree(T);
   depth= GetDepthOfBiTree(T);
     numberOfLeaves=LeafCount(T);
   printf("%d %d\n",depth,numberOfLeaves);
}

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

输入样例：

1 3 0 0 5 7 0 0 0

输出样例：

3 2

解析

/* 请在这里填写答案 */
int GetDepthOfBiTree(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    int left_depth = GetDepthOfBiTree(T->lchild);
    int right_depth = GetDepthOfBiTree(T->rchild);

    if (left_depth > right_depth) {
        return 1 + GetDepthOfBiTree(T->lchild);
    }
    else {
        return 1 + GetDepthOfBiTree(T->rchild);
    }
}
int LeafCount(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    }
    return LeafCount(T->lchild) + LeafCount(T->rchild);
}

1-5 先序输出叶结点

分数 4

作者 陈越

单位 浙江大学

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。

函数接口定义：

void PreorderPrintLeaves( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void PreorderPrintLeaves( BinTree BT );

int main()
{
    BinTree BT = CreatBinTree();
    printf("Leaf nodes are:");
    PreorderPrintLeaves(BT);
    printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

img

Leaf nodes are: D E H I

注意typedef char ElementType;题目中元素是char类型，所以最后输出的时候是printf(" %c", BT->Data);

解析

void PreorderPrintLeaves(BinTree BT) {
    if (BT == NULL) {
        return;
    }
    if (BT->Left == NULL && BT->Right == NULL) {
        printf(" %c", BT->Data);
    }
    PreorderPrintLeaves(BT->Left);
    PreorderPrintLeaves(BT->Right);
}

1-6 层次遍历

分数 3

作者 黄龙军

单位 绍兴文理学院

要求实现函数，输出二叉树的层次遍历序列，可借助STL（标准模板库）之queue（队列）。二叉树采用二叉链表存储，结点结构如下：

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

函数接口定义：

void LevelTraverse(BiTNode* T);

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

裁判测试程序样例：

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

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

void LevelTraverse(BiTNode* T);    // 层次遍历
BiTNode *createBT(string &s);  // 创建二叉树，s存放带虚结点的先序遍历序列

// 根据带虚结点的先序序列创建二叉树并调用层次遍历函数LevelTraverse输出层次遍历结果
int main() {
    string s;
    while(cin>>s) {
        BiTNode* root=createBT(s);
        LevelTraverse(root);
    }    
    return 0;
}

// 请在此处填写答案

// 按字符串s创建二叉树，返回根结点指针
BiTNode *createBT(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=createBT(s);
    p->rchild=createBT(s);
    return p;
}

输入样例：

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

输出样例：

HDGACFBE
-+/axefb-cd

解析

void LevelTraverse(BiTNode* T) {
    if (T == NULL) {
        return;
    }
    queue<BiTNode*> q; // 定义队列存储节点指针
    q.push(T);

    while (q.empty() != true) {
        BiTNode* current = q.front();
        cout << current->data;
        q.pop();

        if (current->lchild != NULL) {
            q.push(current->lchild);
        }
        if (current->rchild != NULL) {
            q.push(current->rchild);
        }
    }
    cout << endl;
}

注意

层次遍历的核心逻辑是：

  1. 若二叉树为空，直接返回（无节点可遍历）。
  2. 初始化队列，将根节点入队。
  3. 循环处理队列中的节点，直到队列为空：
    • 取出队首节点并访问（输出其数据）。
    • 若该节点有左孩子，将左孩子入队。
    • 若该节点有右孩子，将右孩子入队。