首页 > 代码库 > 二叉树中总分支数与总结点数的关系
二叉树中总分支数与总结点数的关系
对任何一个二叉树,若齐叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。证明如下:
设一颗二叉树上叶子结点数为n0,单分支结点数为n1,双分支结点数为n2,则总结点数为:n0+n1+n2。
而一颗二叉树中,所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的两倍,即总分支数=n1+2n2。
由于二叉树中除了根结点以外,每个结点都有唯一的一个分支指向它,因此二叉树中:总分支数=总结点数-1。
即n1+2n2=n0+n1+n2-1。即n0=n2+1。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。