度为4的树:说明该树中结点的最大度数为4(也就是结点的分枝数量最多4个)
度为4的树:

  • 度:某个节点的子节点个数
  • 叶结点:度为0的结点
  • 度为4的树,说明该树中结点的子结点最多为4个
  • 树中结点总个数=(所有的结点的度数)+1
    在树中,除了根节点没有前驱结点,其他节点有且只有一个前驱节点(树的定义)
    又∵ 父结点的‘度’是子结点的个数,而每个子结点前驱结点都是该父结点
    因此,所有结点的“度”加起来,就是把所有结点子结点的个数加起来,又因为,根结点没有父节点,所以所以没有把根结点算计进来,于是:树中结点总个数=(所有的结点的度数)+1(根节点)
    推广→ 一个森林的所有结点数=(所有结点的度数+n(n棵树,每棵树只有一个根节点)

解:设该树的叶结点个数=n0n_0n0
因为叶结点的度为0
总的结点个数sum=n0∗0+n1∗1+n2∗2+...+nm∗m+1(根节点)总的结点个数sum=n_0*0+n_1*1+n_2*2+...+n_m*m+1(根节点)sum=n00+n11+n22+...+nmm+1()
总的结点个数sum=n0+n1+n2+...+nm总的结点个数sum=n_0+n_1+n_2+...+n_msum=n0+n1+n2+...+nm
所以该树的叶结点个数n0=sum−(n1+n2+...+nm)=n1∗(1−1)+n2∗(2−1)+n3∗(3−1)+nm∗(m−1)+1=∑i=1n(i−1)∗ni+1所以该树的叶结点个数n_0=sum-(n_1+n_2+...+n_m)=n_1*(1-1)+n_2*(2-1)+n_3*(3-1)+n_m*(m-1)+1=\sum_{i=1}^n(i-1)*n_i +1n0=sum(n1+n2+...+nm)=n1(11)+n2(21)+n3(31)+nm(m1)+1=i=1n(i1)ni+1

Logo

有“AI”的1024 = 2048,欢迎大家加入2048 AI社区

更多推荐