<分区>
“二叉树中的一个全节点是一个有两个子节点的节点。证明一个(非空)中的全节点个数 二叉树的叶子数少一”
我遇到了这个问题，我不知道它在问我什么，因为我们根本没有在讲座中做过这类问题。它要我做什么以及如何“证明”它？
谢谢
编辑:这是我所做的。我不太确定这是否正确，但问题是我尝试用英语而不是数学来解释它
“考虑到只有一个节点的基本情况，这意味着树只有一个叶子并且没有节点有两个 child 。这比叶子的数量少一个。如果一个节点被添加到一个节点有0个子节点，单节点有2个子节点和叶子个数不变，如果有子节点增加一个节点，2个子节点和叶子节点个数加1，总结, 将节点添加到现有节点是不可能的壮举。二叉树中节点之间的差异将始终比叶数少一个，因为尝试将节点添加到树不会改变或增加叶数树和树叶加 1。”
最佳答案
您的类(class)中所谓的“二叉树”在数学中被称为有根二叉树。只有有根树才有子节点的概念，在无根树中没有父子层次结构，所有节点都是平等的。该陈述仅在一般情况下适用于非空根树。
这里有一个详细的归纳证明。
归纳步骤。假设对于某些正整数 N，对于具有 N 个节点的所有有根二叉树，该语句都是正确的。给定一棵具有 N+1 个节点的 T 树，选择一个叶子 L 并将其删除。结果是一棵 T' 树，有 N 个节点，该陈述为真。假设 L 的父级是 L'。有两种情况:
在这两种情况中的任何一种情况下，叶数和全节点数之间的差异都不会改变。因此，对于所有具有 N+1 个节点的有根二叉树，该陈述都是正确的。
根据归纳法，该命题对所有正整数N都成立。
这个证明的更短(但仍然完全可以接受)的版本如下:
这个答案并不试图解释 mathematical proof 是什么是，或提供构造证明的一般方法。
关于algorithm - 证明二叉树的节点数比叶子数少一，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46882137/