现在我正在研究算法设计教科书中的一个问题,而且我遇到了一些问题.
问题是:
二叉树是一个有根树,其中每个节点最多有两个子节点.通过归纳显示,在任何二叉树中,具有两个子节点的节点数正好比叶子数少一个.
我有理由相信如何做到这一点:基本情况有一个节点,这意味着树有一个叶子,零节点有两个子节点.但是,我不太确定归纳步骤究竟会带来什么.
Moo*_*uck 12
具有单个节点但没有子节点的树(显然)具有/是一片叶子.具有两个子节点(0)的节点数正好比叶子数(1)少一个.
将节点添加到没有子节点的现有节点不会更改具有两个子节点的节点数,也不会更改叶子数.
将节点添加到具有一个子节点的现有节点,将具有两个子节点的节点数增加1,并且还将叶数增加1.
您无法将节点添加到具有任何其他子节点数的现有节点.
由于具有两个子节点的节点的数量恰好比叶子的数量少一个,并且向树中添加节点既不改变数字,也不改变两者,那么它们之间的差异将始终为1.