Skip to content
第4章

4.9 二叉树的属性计算 ​

结点数:先往下交,再往上合 ​

4.8节的遍历,每到一个结点做一件事,比如打印。这一节要的不是做事,而是一个数:整棵树有几个结点、几个叶子、有多高。

本节问题
4.5节那棵二叉树有几个结点、几个叶子、高度是多少?程序怎么算出来?

先看结点数。A不知道整棵树有几个结点,可它知道一件事:二叉树是根、左子树、右子树三样东西。所以整棵树的结点数,等于左子树的结点数,加右子树的结点数,再加根自己这1个。

左右子树各有几个,交给它们自己去数。图里虚线的小箭头是往下交的问题,实线的小箭头是往上带回的答案:

往下交:先问子树。A问两棵子树:你们各有几个结点?B、C也不知道,再往下问。一路问到空树。往下走的这一路,一个数也算不出来。

??????????ABDCG

空树先回答。空树一个结点也没有,答0。这是第一个算得出来的数。

000000ABDCG

往上合:D和G。D收到两个0,加上自己,0 + 0 + 1 = 1,把1报给B。G同样算出1,报给C。

10000100ABDCG

往上合:B和C。B收到左边的1、右边的0,1 + 0 + 1 = 2,报给A。C收到0和1,也算出2。

2210000100ABDCG

往上合:A。A收到两个2,2 + 2 + 1 = 5。整棵树有5个结点。

2210000100A5BDCG

问题是从上往下交下去的,答案是从下往上合回来的。往下的一路只管分,往上的一路才算出数来。

学完这一节,你能用"先往下交、再往上合"的办法,写出求结点数、叶子数、高度这类属性的递归函数。

选中正文里的任意文字,就可以针对它发表评论