Question

数据结构树的结点问题若一棵树中有度数为1至m的各种结点数为n1,n2,…,nm(nm表示度数为m的结点个数)请推导出该树

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.