Stackless предзаказ обход в бинарном дереве

Question

Можно ли выполнить итерационного * предзаказа * обход на бинарное дерево без использования узла-стеки или «посетил» флаги?

Насколько мне известно, такие подходы обычно требуют, чтобы узлы в дереве имели указатели на своих родителей. Теперь, конечно, я знаю, как выполнить предварительный обход с использованием указателей родительских указателей и посещенных флагов, тем самым устраняя любое требование стеков узлов для итеративного обхода.

Но, мне было интересно, нужны ли флаги для посещения. Они занимали бы много памяти, если в дереве было много узлов. Кроме того, наличие у них не имеет большого смысла, если параллельно происходит параллельное проецирование дерева двоичного дерева с предварительным порядком одновременно.

Если это возможно, некоторый псевдокод или лучший пример кода на C++ будет действительно полезен.

EDIT: Я специально не хотят использовать рекурсии для предварительного заказа обхода. Контекст моего вопроса заключается в том, что у меня есть octree (который похож на двоичное дерево), который я создал на графическом процессоре. Я хочу запустить много потоков, каждый из которых выполняет обход дерева независимо и параллельно.

Во-первых, CUDA не поддерживает рекурсию. Seoncdly, концепция посещенных флагов применяется только для одного обхода. Так как много обходов происходит одновременно, поле посещенных полей в структуре данных узла бесполезно. Они будут иметь смысл только на процессоре, где все независимые обходы дерева/могут быть сериализованы. Чтобы быть более конкретным, после каждого обхода дерева мы можем установить флаги, которые были посещены, перед выполнением другого обхода дерева предварительного заказа.

Answer 1

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

Для внутреннего узла, следующий узел в обходе предварительного заказа является его крайним левым ребенком.

Для листового узла: продолжайте движение вверх по дереву, пока вы не перейдете от левого ребенка узла с двумя детьми.Тогда следующий дочерний узел этого узла будет следующим узлом.

function nextNode(node): 
    # inner node: return leftmost child 
    if node.left != null: 
     return node.left 
    if node.right != null: 
     return node.right 

    # leaf node 
    while (node.parent != null) 
     if node == node.parent.left and node.parent.right != null: 
      return node.parent.right 
     node = node.parent 

    return null #no more nodes 

Answer 2

Вы можете добавить один бит на каждом узле, указав, было ли добавлено первое подразделение слева или справа ... Затем, итерация через дерево позволяет выбрать исходное направление в каждой ветви.

Answer 3

Вы можете дать каждому листовому узлу указатель на узел, который будет следующим в соответствии с обходом предзаказов.

Например, если бинарное дерево:

  A 
     /\ 
     B C 
    /\ 
     D E 
      \ 
      F 

D нужно будет хранить указатель на E, и F нужно будет хранить указатель на С. Тогда вы можете просто перемещаться по дереву итеративно, как если бы это был связанный список.

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

Answer 4

Если вы настаиваете на этом, вы можете пронумеровать все возможные пути через дерево, а затем установить для каждого работника, чтобы следовать по этому пути.

Ваша схема нумерации может состоять только в том, что каждый нуль-бит означает левое дочернее устройство, и каждый однобитовый означает принятие правильного дочернего элемента. Чтобы выполнить поиск по глубине, обработайте свой номер от наименее значимого бита до наиболее значимого.

Хотя вам не обязательно знать глубину дерева заранее, если вы этого не сделаете, вам понадобится обработать случай, когда все дальнейшие номера попадут в лист до того, как число будет полностью поглощено.

Answer 5

Существует хак с помощью абсолютных значений из {-> слева, -> правый} указатели для кодирования один бит для каждого узла. Ему нужен первый проход, чтобы получить начальный указатель - «полярность». Кажется, это называется DSW. Вы можете найти в этой статье https://groups.google.com/group/comp.programming/browse_thread/thread/3552ea0af2006b28/6323076923faec26?hl=nl&q=tree+transversal&lnk=nl& нить usenet.

Я не знаю, можно ли его расширить до четырехъярусных деревьев или октов, и я серьезно сомневаюсь, что его можно расширить до многопоточного доступа. Добавление родительского указателя, вероятно, проще ...

Answer 6

В одном направлении, которое вы можете рассмотреть, необходимо удалить узлы дерева при его перемещении и вставить эти узлы в новое дерево. Если вы вставляете узлы в preorder, новое дерево будет точно таким же. Но проблема в том, как вы сохраняете целостность исходного дерева при удалении элементов.