对于那些所有非叶子结点均含有左右子数的二叉树： (1) 试问

[问答题]

对于那些所有非叶子结点均含有左右子数的二叉树：
(1) 试问：有n个叶子结点的树中共有多少个结点？

(2) 试证明：

，其中n为叶子结点的个数，表示第i个叶子结点所在的层次（设根节点所在层次为1）。

推荐

赞花婆

（1）总结点数为1+2_n1，其中n₁为非叶子结点数，则叶子结点数为n=n₁+1，所以总结点数为 2n-1。
（2）用归纳法证明

i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点l₁=1,

设有n个叶子结点时也成立，即

现假设增加一个叶子结点，这意味着在某叶子结点p上新生两个叶子结点，而结点p则成为非叶子结点，可见，总结点数增2，叶子结点数增1。此时，所有叶子结点是原结点除去p，然后加上两个深度为l_p+1的新叶子结点，由此，

则当i=n+1时，也成立，由此即得到证明。

发表于 2018-03-25 10:12:08 回复(0)

提交观点

问题信息

树

上传者：赞花婆

难度：

1条回答 3收藏 2682浏览

扫一扫，把题目装进口袋