Каково общее количество узлов в полном k-арном дереве с точки зрения количества листьев?

Я делаю уникальный форма кодирования Хаффмана, и я строю k-арное (в данном конкретном случае 3-арное) дерево, которое будет полным (каждый узел будет иметь 0 или k дочерних элементов), и я знаю, сколько листьев у него будет, прежде чем я его построю . Как мне рассчитать общее количество узлов в дереве по количеству листьев?

Я знаю, что в случае полного двоичного дерева (2-арного) формула для этого равна 2L - 1, где L - количество листьев. Я хотел бы распространить этот принцип на случай k-арного дерева.

30
задан Andrew 20 October 2011 в 21:19
поделиться