服装网站建设规定,企业网站需求方案,美工做网站是怎么做,申请域名有什么用树的基本性质 ⭐️计算树的总结点与叶结点数#x1f4ab;性质1#x1f4ab;性质2#x1f4ab;例题1#x1f4ab;例题2 ⭐️计算树的总结点与叶结点数
#x1f4ab;性质1
性质1 树中的结点数等于所有结点的度数之和加1 例如上面这棵树#xff0c;A的孩子为B、C、D… 树的基本性质 ⭐️计算树的总结点与叶结点数性质1性质2例题1例题2 ⭐️计算树的总结点与叶结点数
性质1
性质1 树中的结点数等于所有结点的度数之和加1 例如上面这棵树A的孩子为B、C、DA的度数为3B的孩子为E、FB的度数为2C的孩子为GC的度数为1D的孩子为H、ID的度数为2… 结点数A的度数B的度数C的度数D的度数…J的度数K的度数L的度数M的度数1 (BCD)(EF)G(HI)…00001 也就是结点数等于每个结点的孩子树之和(度之和)再加1这个1就是根节点。 总结点数n13; 树的度m3; n0(度为0的结点数)7 n1(度为1的结点数2 n2(度为2的结点数) 2 n3(度为3的结点数)2 n 7 ∗ 0 2 ∗ 1 2 ∗ 2 2 ∗ 3 1 n7*02*12*22*31 n7∗02∗12∗22∗31 性质2
性质2 结点表示个数n为总结点个数 n i {n_i} ni为度为i(0≤i≤m)的结点个数则 n n 0 n 1 . . . n m {nn_0n_1...n_m} nn0n1...nm 对于上面这棵树 总结点树 n13 这树的度数m3 n 0 {n_0} n07; n 1 {n_1} n12; n 2 {n_2} n22; n 3 {n_3} n32; n n 0 n 1 n 2 n 3 n{n_0n_1n_2n_3} nn0n1n2n3 对于上面两种计算树的结点的方法我认为一个是从一个结点本身出发计算它自己本身另一种是从它的孩子出发计算之和 但由于这样树的根节点没有被纪录所以不要忘了加1。
例题1
一颗树度为4的树T中若有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点则树T的叶子结点个数为 A.41 B.82 C.113 D.122 分析 从两种角度出发 从结点自身 总结点 n 20 10 1 10 n 0 n2010110n_0 n2010110n0 从结点的孩子 总结点 n 20 ∗ 4 10 ∗ 3 1 ∗ 2 10 ∗ 1 1 n20*410*31*210*11 n20∗410∗31∗210∗11 联立上面两式可以解得 n 0 82 n_082 n082 例题2
已知一棵树度为m的树中有 n 1 n_1 n1个度为1的结点 n 2 n_2 n2个度为2的结点…, n m n_m nm个度为m的结点问该树中有多少个叶子结点 设总结点n 则 n n 1 n 2 . . . n m n 0 nn_1n_2...n_mn_0 nn1n2...nmn0 且 n 1 ∗ n 1 2 ∗ n 2 3 ∗ n 3 . . . m ∗ n m 1 n1*n_12*n_23*n3...m*n_m1 n1∗n12∗n23∗n3...m∗nm1 联立解得 n 0 n 2 2 n 3 3 n 4 . . . ( m − 1 ) n m 1 n_0n_22n_33n_4...(m-1)n_m1 n0n22n33n4...(m−1)nm1
