假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為.怎么求的？最小高度是一棵三叉樹的高度，除葉子外，每個(gè)節(jié)點(diǎn)有三個(gè)子節(jié)點(diǎn)：將根節(jié)點(diǎn)級(jí)別設(shè)置為1第一級(jí)：1個(gè)節(jié)點(diǎn)第二級(jí)：3個(gè)節(jié)點(diǎn)第三級(jí)：9個(gè)節(jié)點(diǎn)第四級(jí)：27個(gè)

假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為.怎么求的？

最小高度是一棵三叉樹的高度，除葉子外，每個(gè)節(jié)點(diǎn)有三個(gè)子節(jié)點(diǎn)：

將根節(jié)點(diǎn)級(jí)別設(shè)置為1

第一級(jí)：1個(gè)節(jié)點(diǎn)

第二級(jí)：3個(gè)節(jié)點(diǎn)

第三級(jí)：9個(gè)節(jié)點(diǎn)

第四級(jí)：27個(gè)節(jié)點(diǎn)

第五級(jí)：81個(gè)節(jié)點(diǎn)

1 39 27=40 50

所以最小值是高度是5

一棵深度為N的三叉戟樹有3^0 3^1。。。3^（n-1）=（3^n-1）/2

]（3^n-1）/2

，所以如果最小值是3

，最大值是50

因?yàn)槿鏄渲兴泄?jié)點(diǎn)的階數(shù)不大于3，所以節(jié)點(diǎn)總數(shù)（表示為n）應(yīng)該等于0階節(jié)點(diǎn)，1階節(jié)點(diǎn)（表示為N1）的和，2度節(jié)點(diǎn)（N2）和3度節(jié)點(diǎn)（N3）：n=no N1 N2 N3（公式1）另一方面，1度節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，2度節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，3度節(jié)點(diǎn)有三個(gè)子節(jié)點(diǎn)。因此，三叉樹中的子節(jié)點(diǎn)總數(shù)為：NL 2n2 3n3樹只有根節(jié)點(diǎn)不是任何節(jié)點(diǎn)的子節(jié)點(diǎn)，因此二叉樹中的節(jié)點(diǎn)總數(shù)可以表示為：n=N1 2n2 3n3 1（公式2）。由式1和式2得到：no=N2 2n3 1