当前位置 : 主页 > 编程语言 > java >

【数据结构】二叉树节点总数与度数,边数的关系

来源:互联网 收集:自由互联 发布时间:2022-06-30
我们设度为0,1,2的节点分别为n0,n1,n2个,那么节点总数n=n0+n1+n2,然而边数b=n-1(除去最顶上的节点),并且b=n1+2*n2=n-1=n0+n1+n2-1,由此我们可以推出n0=n2+1 也就是说叶子节点要比度为二的节点

我们设度为0,1,2的节点分别为n0,n1,n2个,那么节点总数n=n0+n1+n2,然而边数b=n-1(除去最顶上的节点),并且b=n1+2*n2=n-1=n0+n1+n2-1,由此我们可以推出n0=n2+1

也就是说叶子节点要比度为二的节点多一个。
b=n1+2*n2 度为2的节点有两条边,度为1的节点有1条

结点总数=度数*该度数对应的结点数+1
n=n2 *2+n1 *1+0 *n0+1

因为度为2的节点连接两个节点,度为1的节点连接一个节点,最后加1个最顶端的根节点就行

总结

  • 节点总数n=n0+n1+n2
  • 边数等于b=n-1=n1+2* n2
  • 由1,2推出 n0=n2+1

  • 上一篇:【笔试题目】小米2020秋招测试开发
    下一篇:没有了
    网友评论