数据结构树的结点问题

Question

若一棵树中有度数为1至m的各种结点数为n1,n2,…,nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。

Answer 1

在一棵树中，每条边都可以确定一对父结点和子结点。除了根结点之外，所有的结点都拥有父结点。所有结点的数量=n0+n1+n2+...+nm,因为只有1个根结点没有父结点，所以树中的总边数=所有结点的数量-1=n0+n1+n2+...+nm-1. 在从子结点方面上计算，总边数=1*n1+2*n2+...+m*nm. 这样，可以建立方程: n0+n1+n2+...+nm-1=1*n1+2*n2+...+m*nm. 所以n0=n2+2*n3+3*n4+...+(m-1)*nm+1.