Общее количество узлов в древовидной структуре данных?
Чтобы убедиться, что проверка XHTML работает правильно, когда у вас есть JavaScript, встроенный в вашу страницу, а не с внешней ссылкой.
XHTML требует, чтобы ваша страница строго соответствовала требованиям разметки XML. Поскольку JavaScript может содержать символы со специальным значением, вы должны обернуть их в CDATA, чтобы убедиться, что проверка не означает, что он неверен.
С HTML-страницами в Интернете вы можете просто включить требуется JavaScript между и тегами. Когда вы проверяете HTML на своей веб-странице, содержимое JavaScript считается CDATA (символьные данные), которое поэтому игнорируется валидатором. То же самое не верно, если вы следуете более поздним стандартам XHTML при настройке своей веб-страницы. С XHTML код между тегами скрипта считается PCDATA (анализируемые символьные данные), который поэтому обрабатывается валидатором.
Из-за этого вы не можете просто включать JavaScript между тегами сценария на своем страницы без «взлома» вашей веб-страницы (по крайней мере, насколько это касается валидатора).
blockquote> blockquote>Вы можете узнать подробнее о CDATA здесь и подробнее о XHTML здесь .
5 ответов
Хорошо, каждый узел имеет о подузлах N, и дерево является уровнями L глубоко.
With 1 level, the tree has 1 node.
With 2 levels, the tree has 1 + N nodes.
With 3 levels, the tree has 1 + N + N^2 nodes.
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes.
общее количество узлов (N^L-1) / (N-1).
хорошо, просто небольшой пример, почему, это экспоненциально:
[NODE]
|
/|\
/ | \
/ | \
/ | \
[NODE] [NODE] [NODE]
|
/|\
/ | \
Формула для вычисления суммы узлов подробно L: (Учитывая, что существуют корневые узлы N)
Н <глоток> L
Для вычисления количества всех узлов, нужно сделать это для каждого слоя:
for depth in (1..L)
nodeCount += N ** depth
, Если существует только 1 корневой узел, вычтите 1 из L и добавьте 1 к общему количеству узлов.
знать, что, если в одном узле сумма листов отличается от среднего случая, это может оказать большое влияние на Ваше число. Чем далее в дереве, тем больше влияния.
* * * N ** 1
*** *** *** N ** 2
*** *** *** *** *** *** *** *** *** N ** 3
Это - общественная Wiki, поэтому не стесняйтесь изменять мою ужасную алгебру.
-
1"!! " переменная в ударе, тем не менее, таким образом, одинарные кавычки требуются. – Joe Kington 28 July 2010 в 05:43
Если Вы не знаете ничто иное кроме глубины дерева затем Ваша единственная опция для разработки, что общий размер состоит в том, чтобы пройти и считать их.
-
1
Если Ваше дерево - приблизительно полные , который является каждым уровнем, имеет его полное дополнение детей за исключением последних двух, то Вы имеете между вершинами N^(L-2) и N^(L-1) и между N^(L-1) и общим количеством узлов N^L.
, Если Ваше дерево не полно, то знание количества вершин не помогает, поскольку полностью несбалансированное дерево будет иметь одну вершину, но произвольно много родителей.
интересно, как точный Ваш оператор 'каждый узел имеет об узлах N', - если Вы знаете средний коэффициент ветвления, возможно, можно вычислить ожидаемый размер дерева.
, Если Вы можете найти отношение листов к внутренним узлам, и Вы знаете среднее число детей, можно приблизить это как (n*ratio) ^N = n. Это не даст Вам Ваш ответ, но интересно, может ли кто-то с лучшей математикой, чем я выяснить способ вставить L в это уравнение и дать Вам что-то разрешимое.
однако, если Вы хотите знать точно, необходимо выполнить итерации по структуре дерева и узлов количества, когда Вы идете.
-
1Двойные / одинарные кавычки, оба работал бы то же в этом примере. Различие - это одинарные кавычки don' t разворачивают $VARIABLES, и двойные кавычки делают. mpi-inf.mpg.de/~uwe/lehre/unixffb/quoting-guide.html – adamJLev 28 July 2010 в 05:17
Just to correct a typo in the first answer: the total number of nodes for a tree of depth L is (N^(L+1)-1) / (N-1)... (that is, to the power L+1 rather than just L).
This can be shown as follows. First, take our theorem:
1 + N^1 + N^2 + ... + N^L = (N^(L+1)-1)/(N-1)
Multiply both sides by (N-1):
(N-1)(1 + N^1 + N^2 + ... + N^L) = N^(L+1)-1.
Expand the left side:
N^1 + N^2 + N^3 + ... + N^(L+1) - 1 - N^1 - N^2 - ... - N^L.
All terms N^1 to N^L are cancelled out, which leaves N^(L+1) - 1. This is our right hand side, so the initial equality is true.