PTA（树和二叉树）1-3 求二叉树的高度

zhangzhang2025-11-062025-11-06

1-3 求二叉树的高度

分数 5

作者 YJ

单位西南石油大学

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

函数接口定义：

1	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;
}

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

输入样例：

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

1	AB##CD##EF###

输出样例：

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

答案

int Depth(BiTree Tree) {
    int m, n;
    if (Tree == NULL) { // 如果是空树，深度为0, 递归结束
        return 0;
    } else {
        m = Depth(Tree->lchild); //递归计算左子树的深度记为m
        n = Depth(Tree->rchild); //递归计算右子树的深度记为n
        if (m > n) { // 二叉树的深度为m与n的较大者加1
            return m + 1;
        } else {
            return n + 1;
        }
    }
}

示例二叉树结构

假设我们有如下二叉树（节点中的数字仅用于区分，无实际意义）：

    A
   / \
  B   C
 /   / \
D   E   F
   /
  G

函数计算过程（递归拆解）

Depth 函数的核心逻辑：树的深度 = 左子树深度与右子树深度的最大值 + 1（当前节点自身的层数）。

我们从根节点 A 开始逐步递归计算：

1. 计算根节点 `A` 的深度

需要先计算其左子树（B 为根）的深度 m，和右子树（C 为根）的深度 n。

2. 计算左子树（根节点 `B`）的深度 `m`

节点B的左子树是D，右子树是NULL。
- 计算B的左子树D的深度：
  - 节点D的左、右子树都是NULL，因此：
    - Depth(D->lchild) = 0（空树深度为 0）
    - Depth(D->rchild) = 0
    - 所以 Depth(D) = max(0, 0) + 1 = 1（D 自身为 1 层）
- 计算 B 的右子树（NULL）的深度：Depth(NULL) = 0
- 因此，Depth(B) = max(Depth(D)=1, 0) + 1 = 1 + 1 = 2 → 即 m = 2。

3. 计算右子树（根节点 `C`）的深度 `n`

节点C的左子树是E，右子树是F。
- 计算C的左子树E的深度：
  - 节点E的左子树是G，右子树是NULL。
    - 计算 G 的深度：G 的左、右子树都是 NULL，因此 Depth(G) = max(0, 0) + 1 = 1
    - 计算 E 的右子树（NULL）的深度：0
    - 所以 Depth(E) = max(Depth(G)=1, 0) + 1 = 1 + 1 = 2
- 计算C的右子树F的深度：
  - F 的左、右子树都是 NULL，因此 Depth(F) = max(0, 0) + 1 = 1
- 因此，Depth(C) = max(Depth(E)=2, Depth(F)=1) + 1 = 2 + 1 = 3 → 即 n = 3。