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

1-3 求二叉树的高度

分数 5

作者 YJ

单位 西南石油大学

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

函数接口定义：

1
int Depth(BiTree Tree);

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

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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###

输出样例：

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

1
4

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
        }
    }
}

示例二叉树结构

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

1
2
3
4
5
6
7
    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。

4. 回到根节点 A

根节点 A 的深度 = max(m=2, n=3) + 1 = 3 + 1 = 4。