Алгоритм рекурсии для генерации карты сайта

Question

У меня есть DataTable, содержащая иерархию карты сайта со следующими столбцами:

• ItemId
• ParentId
• Имя
• 1010 * Url *

Мне нужно создать набор вложенных списков в HTML (для ясности опущены якорные элементы):

<ul>
<li>Item 1</li>
<li>Item 2</li>
    <ul>
    <li>Sub Item 1</li>
    <li class="current">Sub Item 2</li>
    </ul>
<li>Item 3</li>
</ul>

Дерево должно содержать только ветви, которые ведут к «текущему» узлу / странице (поэтому, используя приведенный выше пример, любые дочерние элементы, которые имеют элемент «1» или «3», не отображаются. Может кто-нибудь помочь с каким-нибудь псевдокодом / Пример кода, который может перемещаться по дереву от листа к корню, создавая HTML, как он есть? Спасибо.

Answer 1

Более эффективный способ сделать это, если вы можете изменить структуру данных, это использовать вложенные наборы:

Управление иерархическими данными в MySQL

Использование модели данных Nested Set для ссылок Breadcrumb

Answer 2

Вот какой-то псевдокод. Идея проста: начните со всех немаркированных узлов и отметьте родительский узел вашего текущего узла, его родительский и т. Д., Пока не дойдете до корня. Делая это, вы пометите точно узлы на пути от вашего текущего узла к корню. Затем вы можете просто напечатать все узлы за один проход, повторяя только на «помеченных» узлах. Это оптимально (время выполнения - самое большее количество узлов, которые вы должны распечатать).

for all n: mark[n]=False
n=current
while n!=root:
    n=parent[n]
    mark[n]=True

def print_tree(n):
    print_node(n)
    if mark[v]==True:
        print '<ul>'
        for each child c of n: print_tree(c)
        print '</ul>'

def print_node(n):
   if n==current: print '<li class="current">' else: print '<li>'
   print name[n]
   print "</li>"

print_tree(root)

parent[n] и name[n] - это, вероятно, что-то вроде n.parent и n.name в вашей структуре. Что касается части "для каждого дочернего элемента n" - я предполагаю, что у вас есть список смежности, в котором содержится список всех дочерних элементов данного узла. (Если нет, то в каком порядке следует печатать дочерние элементы?). В любом случае, списки смежности можно построить за время O (количество узлов), просто добавив каждый узел в список «дочерних элементов» его родитель. Размер списков total не превышает количество узлов (поскольку каждый узел, отличный от корня, находится ровно в одном из списков), поэтому эти списки не занимают много памяти (один список может содержать много элементов, но общий размер ограничен).

Answer 3

Это VBScript, и хотя я не пытался его запустить, поэтому он может содержать ошибки, он должен дать вам основную идею.

'# OMITTED: Code to retrieve the record for the current node, and read all info about it.
'# Note: field values are read into variables with the same names.

Dim RootFound
Dim ListHTML
RootFound = false
ListHTML = ""

if ParentID = Null then RootFound = true
ListHTML = "<ul><li>" & Name & "</li></ul>"

while not RootFound
  SQL = "SELECT * FROM DataTable WHERE ItemID = " & ParentID
  '# OMITTED: Code to open dataset using the SQL statement above and 
  'fetch all field values into identically named variables

  ListHTML = "<ul><li>" & Name & "</li>" & ListHTML & "</ul>"
  if ParentID = Null then RootFound = true
wend

Answer 4

Я сделал что-то похожее, оно может быть не таким эффективным, но его легко отладить.

1. Найти путь к выбранному узлу.
2. Добавление корневых узлов в список.
3. Найти узел в списке, который находится в пути.
4. Добавьте всех детей в этот узел.
5. Найти следующий узел в пути.
6. Повторите 4-5, пока на выбранном узле, а если нет на листе, добавьте также выбранные узлы childern.

Альтернатива: 1. Найти выбранный узел, распечатать этот и все братья и сестры 2. Напечатайте родителя и всех братьев и сестер вокруг строки из 1. 3. Повторите 2 до корня.