二叉树的顶点_java

资料来源：网络整理时间：2023/3/7 1:22:18 共计：3548 浏览

二叉树的顶点？

分析一些树的算法时，我们常常需要以给定的二叉树的顶点数n(T) 来度量问题实例的规模。而这个顶点数n(T) 指的就是树的扩展形式中所有顶点的个数，这些顶点分两类，一类是外部顶点，一类就是内部顶点。根据定义，一颗扩展的空二叉树是一个单独的外部顶点。

为了确定一些算法(递归的求树的高度，递归的前序、中序、后续遍历，求叶节点数等等)的效率，我们需要知道一颗包含n 个内部顶点的扩展二叉树最多能够具有几个外部顶点。考察几个例子后，我们容易做出这种假设：外部顶点的数量x 比内部顶点的数量大一，即

x = n + 1。

在n ≥ 0 的情况下，我们对内部顶点使用强数学归纳法来证明该等式。

归纳基础：n = 0 时，根据定义，一颗空树只有一个外部顶点，满足等式 x = n + 1。

归纳假设：假设当任意二叉树具有0 ≤ k ≤ n 个内部顶点时，x = k + 1。

下面我们证明当k = n + 1 时命题依然成立。不失一般性，假设T 的左子树的内部顶点和外部顶点的个数分别是nL 和 xL，T 的右子树的内部顶点和外部顶点的个数分别是nR 和xR，左右子树内部节点的个数满足我们的归纳假设，因此我们有

x = xL + xR = (nL+1) + (nR+1) = n + 1。命题得证。

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。