外观
4.9 二叉树的属性计算
结点数:先往下交,再往上合
4.8节的遍历,每到一个结点做一件事,比如打印。这一节要的不是做事,而是一个数:整棵树有几个结点、几个叶子、有多高。
本节问题4.5节那棵二叉树有几个结点、几个叶子、高度是多少?程序怎么算出来?
先看结点数。A不知道整棵树有几个结点,可它知道一件事:二叉树是根、左子树、右子树三样东西。所以整棵树的结点数,等于左子树的结点数,加右子树的结点数,再加根自己这1个。
左右子树各有几个,交给它们自己去数。图里虚线的小箭头是往下交的问题,实线的小箭头是往上带回的答案:
往下交:先问子树。A问两棵子树:你们各有几个结点?B、C也不知道,再往下问。一路问到空树。往下走的这一路,一个数也算不出来。
空树先回答。空树一个结点也没有,答0。这是第一个算得出来的数。
往上合:D和G。D收到两个0,加上自己,0 + 0 + 1 = 1,把1报给B。G同样算出1,报给C。
往上合:B和C。B收到左边的1、右边的0,1 + 0 + 1 = 2,报给A。C收到0和1,也算出2。
往上合:A。A收到两个2,2 + 2 + 1 = 5。整棵树有5个结点。
问题是从上往下交下去的,答案是从下往上合回来的。往下的一路只管分,往上的一路才算出数来。
学完这一节,你能用"先往下交、再往上合"的办法,写出求结点数、叶子数、高度这类属性的递归函数。
叶子数和高度:只换合的办法
叶子数、高度和结点数一样:先往下交,问到空树;再往上合。往下交的路线完全一样,不同的只是往上合的时候怎么算。
叶子数。空树没有叶子,答0。D的两棵子树都是空的,D自己就是叶子,报1;G也报1。B收到1和0,自己不是叶子,只把两边加起来,报1;C也报1。A收到1和1,得2。
高度。空树的高度是0。D收到0和0,取大的,再加上自己这一层,0 + 1 = 1。B收到1和0,取大的1,加1得2;C也是2。A收到两个2,得3。
三个问题,合回来的办法各不相同:结点数是两边相加再加1;叶子数是叶子报1,别的结点只把两边相加;高度是两边取大的再加1。
回到本节问题。这棵树有5个结点、2个叶子,高度是3。
递下去,归上来
3.8节把递归分成两半:递,是一层一层调用下去;归,是一层一层返回上来。算二叉树的属性,两半各干各的事。递的时候,把问题交给两棵子树,一直交到空树;归的时候,把两棵子树带回的答案和根合起来。
写这类函数,只要回答三个问题:
- 空树的答案是多少?递到底时,直接返回它。
- 根自己算多少?
- 两棵子树带回的答案,怎么和根合起来?
后两问,都在归的时候做。三个属性的回答汇总起来:
| 空树 | 根自己 | 怎么合 | |
|---|---|---|---|
| 结点数 | 0 | 1 | 左 + 右 + 1 |
| 叶子数 | 0 | 是叶子算1,否则0 | 叶子直接报1,否则左 + 右 |
| 高度 | 0 | 一层 | 左、右里大的 + 1 |
和遍历比一比。4.8节的先序遍历,在往下走的路上就打印了,返回时什么也不带回来。函数是void,递归调用写成一条语句:
c
PreOrder(T->lchild);算结点数,答案要带回来交给双亲。函数返回int,递归调用写成一个值,放进算式里:
c
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;多出来的返回值,就是那条往上合的路。要先等两棵子树的答案回来,才能算根,这正是4.8节说的后序:先做完孩子,再做自己。只是这里的"做",变成了"算"。
写成函数
用4.7节的二叉链表,三问各写成一行:
c
int NodeCount(BiTree T) {
if (T == NULL) return 0; /* 空树:0个 */
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
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);
}
int Depth(BiTree T) {
if (T == NULL) return 0; /* 空树:高度0 */
int l = Depth(T->lchild);
int r = Depth(T->rchild);
return (l > r ? l : r) + 1; /* 大的那个,加上根这一层 */
}每个函数的第一行回答第一问,最后一行回答后两问。Depth先把两边的答案存进l、r,再比大小,这样每棵子树只算一次。
要多少时间和空间。和4.8节的遍历一样,每个结点调用一次,空指针也各调用一次,时间是O(n);递归最深等于树的高度,空间是O(h)。
完整程序搭出4.5节那棵树,算出三个属性:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
int NodeCount(BiTree T) {
if (T == NULL) return 0; /* 空树:0个 */
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
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);
}
int Depth(BiTree T) {
if (T == NULL) return 0; /* 空树:高度0 */
int l = Depth(T->lchild);
int r = Depth(T->rchild);
return (l > r ? l : r) + 1; /* 大的那个,加上根这一层 */
}
/* 释放是后序:先释放两棵子树,再释放根 */
void Destroy(BiTree T) {
if (T == NULL) return;
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
}
int main(void) {
/* 搭出4.5节那棵树,做法和4.7节一样 */
BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = 'A';
T->lchild = NULL;
T->rchild = NULL;
BiTNode *b = (BiTNode *)malloc(sizeof(BiTNode));
b->data = 'B';
b->lchild = NULL;
b->rchild = NULL;
T->lchild = b;
BiTNode *c = (BiTNode *)malloc(sizeof(BiTNode));
c->data = 'C';
c->lchild = NULL;
c->rchild = NULL;
T->rchild = c;
BiTNode *d = (BiTNode *)malloc(sizeof(BiTNode));
d->data = 'D';
d->lchild = NULL;
d->rchild = NULL;
b->lchild = d;
BiTNode *g = (BiTNode *)malloc(sizeof(BiTNode));
g->data = 'G';
g->lchild = NULL;
g->rchild = NULL;
c->rchild = g;
printf("结点数:%d\n", NodeCount(T));
printf("叶子数:%d\n", LeafCount(T));
printf("高度:%d\n", Depth(T));
Destroy(T);
return 0;
}text
结点数:5
叶子数:2
高度:3例题:度为2的结点有几个
题目写一个函数,求二叉树里度为2的结点有几个。用4.6节6个结点的完全二叉树验算,再看它和叶子数的关系。
分析。照三问来写:
- 空树的答案:没有结点,答0。
- 根自己算多少:两个孩子都在,度是2,算1;否则算0。
- 怎么合:左边带回的,加右边带回的,再加根自己的。
c
int Degree2Count(BiTree T) {
if (T == NULL) return 0;
int self = (T->lchild != NULL && T->rchild != NULL) ? 1 : 0;
return Degree2Count(T->lchild) + Degree2Count(T->rchild) + self;
}在6个结点的树上,从下往上合:
叶子报0。D、E、F都没有孩子,自己算0,两边带回的也是0,报0。
B和C。B有两个孩子,0 + 0 + 1 = 1。C只有左孩子,自己算0,0 + 0 + 0 = 0。
A。A有两个孩子,1 + 0 + 1 = 2。
这棵树的叶子是D、E、F,3个。3 = 2 + 1,正是4.6节的性质:叶子比度为2的结点多一个。
答案度为2的结点有2个,A和B。叶子3个,比它多一个。
练习1:度为1的结点有几个
填空
照三问,写求度为1的结点数的函数:
- 空树返回
- 根自己:恰好有一个孩子时算 ,否则算0
- 合起来:左边带回的 右边带回的,再加根自己的
- 4.5节那棵树里,度为1的结点有 个
B只有左孩子,C只有右孩子,度都是1,一共2个。合的时候要把两边都数上,所以是相加,不是取大的。
练习2:写错的Depth
单选
A
3
3是高度。可这一行把两边相加了,不是取大的。
B
5
两边相加再加1,正是数结点的合法。它算出来的是结点数5。
C
2
2是叶子数。叶子数在叶子处报1,别处不加1。
D
6
每个结点只加一次1,一共5个结点。
合的办法换了,算出来的就是另一个属性。
练习3:每棵子树带回的高度
填空
对这棵二叉树调用Depth:
- 以E为根的子树,带回
- 以B为根的子树,带回
- 整棵树的高度是
F报1,E收到1和0,取大的加1得2。B收到D的1和E的2,取大的加1得3。A收到3和C的1,得4。
到这里你有了求二叉树的属性,先递下去,把问题交给两棵子树,一直交到空树;再归上来,把两棵子树带回的答案和根合起来。写函数时回答三问:空树答什么,根自己算多少,两边怎么合。结点数、叶子数、高度、度为2的结点数都这样算。它是后序,时间O(n),空间O(h)。下一步给出一棵树,能写出它的序列。反过来,给出序列,能不能把树建回来?