Обход дерева

Тема в разделе "WASM.A&O", создана пользователем Mika0x65, 19 авг 2007.

  1. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Мое почтение всем.

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

    Код (Text):
    1. ptr = root;
    2. while(1)
    3. {
    4.         //тут делаем что хотим.
    5.  
    6.         //если можно идти влево -- всегда идем влево.
    7.         if (ptr ->left)
    8.         {
    9.                 ptr = ptr ->left;
    10.         }
    11.         else
    12.         {
    13.                 //раз нельзя -- будем подниматься по всем узлам,
    14.                 // пропуская все, где мы уже были справа.
    15.                 ptr = ptr ->parent;
    16.                 while (ptr ->parent && ptr ->traversed)
    17.                 {
    18.                         ptr = ptr ->parent;
    19.                 }
    20.  
    21.                 //если дошли до корня, и побывали у него справа --
    22.                 // дерево обойдено.
    23.                 if (ptr ->parent == NULL && ptr ->traversed)
    24.                         break;
    25.  
    26.                 //а раз нет -- ставим признак и идем вправо.
    27.                 ptr ->traversed = 1;
    28.                 ptr = ptr ->right;
    29.         }
    30. }
    Так вот, мне интересно, можно ли обойти дерево без введения признака? Варианты с самодельным стеком я откидываю, т.к. это шило на мыло (ну, не так, конечно, но все же). Думаю, что без признака нельзя, но вдруг все же можно?
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    можно обойти и без признака. почитай на эту тему, у Кнута, наверняка, есть.
     
  3. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Как?
    Кнута, к сожалению, под рукой ни в каком виде нет.
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Mika0x65
    из каждого узла выходит k ветвей: достаточно знать сколько ветвей мы прошли в узле и общую сумму пройденных узлов- отсюда и считается на сколько узлов в верх нужно прыгнуть.
     
  5. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Mika0x65
    Зависит от дерева. Если соседние узлы (? siblings) упорядочены и определена функция сравнения узлов(равно - не равно), то можно и без признака. Иначе потребуется хранить дополнительную информацию о пройденном пути, которую тогда можно будет обозвать "самодельным стеком" (хотя это и не обязан, естественно, быть стек).
     
  6. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Stiver
    не важно упорядочено дерево или нет: нужно лишь перебирать ветви каждого узла (не важно в каком порядке, если требуеться полный обход дерева), а затем переходить к соседнему узлу, вот, например:
    a1->b1->c1
    a1->b1->c2
    a1->b2->c3
    a1->b2->c4
     
  7. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    UbIvItS
    А можно подробнее? Я не совсем понял, что даст кол-во узлов. Лучше всего псевдокод, типа того, что я привел на asm/C.
     
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Mika0x65
    код строкать как-то влом - объясню на пальцах: кол-во ветвей на нижнем этаже равно A^k, A - колво веток в узле; k- высота дерева. спускаемся в нижнюю левую ветвь дерева и начинем обход всех ветвей в узле; как пройдено A ветвей мы смотрим с какого верхнего узла нужно проводить спуск в низ (мда........ несколько витеевато я настрокал:))) давай по другому: представь себе число с основанием A и колвом разрядов k ====> перебор всех его значений и есть обход дерева.
     
  9. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    точней перебор всех значений 10.....0
     
  10. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    UbIvItS
    Витеевато -- это мягко сказано...
     
  11. JAPH

    JAPH New Member

    Публикаций:
    0
    Регистрация:
    23 июн 2007
    Сообщения:
    124
    Писал прям в форум, не факт что работает :) но вроде должно :)
    Предположение - дерево, у которого по две ветви из каждого узла, дерево полное.
    Код (Text):
    1. p = root -> right -> right -> right -> right -> right; // самая правая вершина
    2. unsigned i = 1 << 5; // для дерева высоты 5
    3. while (--i) {
    4.     signed c;
    5.     donothing(p);
    6.     __asm bsf ecx, i; __asm mov c, ecx; __asm push ecx;
    7.     while (c--) p = p -> parent;
    8.     donothing(p -> parent); // если обходить не только листья
    9.     p = p -> parent -> left;
    10.     __asm pop c;
    11.     while (c--) p = p -> right;
    12. }
    13. donothing(p);
     
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Mika0x65
    лано, давай для удобства бинарное дерево рассмотрим в 3 этажа: первая крайняя ветвь с лева имеет код 100b, а с права 111b, тоесть обход всех ветвей - это перебор всех значений счётчика. теперь давай вспомним особеность древовидной СД: мы не можем к произвольному узлу обратиться произвольно - нужно пройти всех его прародителей. тоесть, для обращение к соседу мы должны дойти до их общего родителя в верх и только затем спустится к соседнему узлу на том же уровне, например: узлы a->b1->a1 & a->b2->a3 имеют общего родителя a[\b], тогда как a->b1->a1 & a->b1->a2 имеют общего родителя b1.
     
  13. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Где-то на форуме эта задача была, но найти не смог. Решение там было примерно такое:

    cur - текущий узел
    from - узел из которого пришли
    Код (Text):
    1. cur = root;
    2. from = END;// маркер для определения конца обхода, не равный NULL
    3.  
    4. do{
    5.   do{
    6.     temp = cur->left;
    7.     cur->left = cur->right;
    8.     cur->right = from;
    9.     from = temp;
    10.   }while(from==NULL);
    11. [добавлено]
    12.   if(from>cur->left && from>cur->right)
    13.   //сравниваются адреса, END должен быть больше чем NULL
    14.   {
    15.     //здесь обрабатываем узел
    16.     //узлы будут обрабатываться по одному разу
    17.     //но произойти это может как при спуске, так и при подъёме или переходе в другое поддерево
    18.   }
    19. [/добавлено]
    20.   temp = cur;
    21.   cur = from;
    22.   from =temp;
    23. }while(cur!=END);
    [удалено]Правда каждый узел здесь посещается несколько раз, как это обойти пока не знаю, возможно есть и другие баги.[/удалено]
     
  14. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Помойму без разметки во время прохода, или повторного посещения сделать это никак нельзя. Единственная надежда это опираясь на мысли UbIvItS следить за путевой меткой узлов. Спускаемся влево - дописываем ноль, спускаемся вправо еденицу, поднимаемся, убираем один разряд. Таким образом образуемое число всегда должно возрастать, и мы защищены от повторов. Но узнать в каком направлении мы идём по узлу - это значительная проблема. Спуск и подъём отличить алгоритм отличать позволяет. А вот лево от право нет. Единственная зацепка, это принудительно поддерживать узлы в неком специфичном состоянии, когда адрес родительского и дочерних узов расположены в памяти с определённом порядке. Скажем родитель по адресу меньше нашего узла. А у сынков, второй узел по адресу меньше первого. Тогда сравнивая адрес можно догадываться о направлении. Для этого придётся как минимум для кажлого узла держать адрес родителя, чтобы при обмене телами между родителем и текущим узлом, можно было коректировать ссылку на родителя (тут точнее даже нужна ссылка на родителя, а ссылка на ссылку на текущий узел внутри родителя нашего узла).
    Ну а если можно сравнивать сами значения, то ещё проще...

    Так что стоит ли оно такого гемора, если можно просто выполнять разметку узлов при обходе?
     
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Proteus
    что такое узел дерева - это просто сишная struct c ссылками на другие узлы ==========> перебор этих ссылок в узле вполне определён, например, если адрес у нас 4 байта, то смещаясь в структуре(узле) на 4*i байт мы получаем новую ветвь. счётчик позволяет исключить повторы.
     
  16. Miller Rabin

    Miller Rabin New Member

    Публикаций:
    0
    Регистрация:
    4 янв 2006
    Сообщения:
    185
    Это типа вариант с "самодельным стеком" чем тебе такое решение не нравится я х.з. По-крайне мере оно точно эффективнее чем выделение признака или того хуже создания массива пройденных вершин.

    Обход в глубину
    Код (Text):
    1. proc Tree Tree
    2. push esi
    3. ;Начинаем обход с корня дерева
    4. mov esi, [Tree.Root]
    5. test esi, esi                                                   ;А есть ли корень?
    6. je .lbEnd
    7.  
    8. ;Сохраняем значение стека
    9. mov edx, esp
    10.  
    11. .lbNextNode
    12.   mov eax, DWORD[esi]                                     ;TreeNode.Node Указатель на массив детей элемента дерева
    13.   mov ecx, DWORD[esi+4]                                  ;TreeNode.NodesCount Количество детей в эелементе дерева
    14.   ;В esi хранится текущий элемент дерева тут его можно вывести на экран или куда там еще
    15.  
    16.   test eax, eax                                                 ;Проверяем, а есть ли в элементе дерева что-нибудь?
    17.   je .lbGetParent                                               ;Если нет, то на уровень выше
    18.   test ecx, ecx
    19.   je .lbGetParent  
    20.  
    21.   push eax                                                      ;Сохраняем в стеке нашу текущую позицию
    22.   push ecx
    23.  
    24. .lbNextNodeItem:
    25.   mov esi, DWORD [eax+ecx*4-4]                       ;переходим к самому последнему ребенку дерева
    26.   test esi, esi                 ;проверяем его на 0
    27.   jne .lbNextNode                              ;если он не нулевой, то работаем с ним как с новым элементом дерева
    28.   sub ecx, 1                                                   ;иначе уменьшаем счетчик элементов на 1
    29.   jnz .lbNextNodeItem                      ;если у нас еще остались непросмотренные элементы, то берем следующий элемент
    30.  
    31. .lbGetParent:                   ;Пытаемся вернуться на уровень вверх
    32.   cmp edx, esp                  ;Проверяем можно ли поднятся на уровень вверх
    33.   je .lbEnd                 ;Если нельзя, то мы все уже обработали надо выходить
    34.   pop ecx                   ;Восстанавливаем верхний уровень
    35.   pop eax  
    36.  
    37.   sub ecx,1                                                    ;Так как в этом уровне 1 элемент мы только что обработали уменьшаем счетчик
    38.   jnz .lbNextNodeItem                                       ;Если на этом уровне остались еще необработанные элементы, то обрабатываем их
    39.   jmp .lbGetParent              ;Иначе переходим еще на уровень выше
    40.  
    41. .lbEnd:                                                          ;Это конец
    42.   pop esi
    43.  ret
    44. endp
     
  17. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    фишка в том что решение не намногим лучше самой рекурсии. Вызываешь ты функцию обхода и ставишь стек самодельный или родной , смысл уже теряется.
     
  18. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    в узле порядок ссылок определён. Но мы обходим дерево производя при этом престройку ссылок (перезацепку узлов). Поэтому идём вы по узлу вверх, влево, вправо, Процедура в какдом направлении используется одна и та же.
    Сама трудность в том чтобы понять в каком направлении идёт обход.
     
  19. Miller Rabin

    Miller Rabin New Member

    Публикаций:
    0
    Регистрация:
    4 янв 2006
    Сообщения:
    185
    Proteus
    1. Ну оно лучше рекурсии хотя бы тем, что жрет памяти минимум на треть меньше ну и предположительно быстрее.
    2. Использование идентификаторов внутри элементов дерева так же требует ровно столько же памяти (4 байта на индекс и 4 байта на адрес возврата). Плюс неэффективно в многопоточных системах.
    3. Тем что ты располагаешь элементы дерева в памяти особым образом (чем выше элемент в дереве тем меньше его адрес), ты превращаешь дерево в обычный массив. И эффективность работы с таким деревом будет такая же как с обычным массивом.
    4. Использование отдельного массива для хранения счетчиков это вообще полный абзац. Глубина дерева заведомо ограничена размером массива. Уж лучше рекурсия.
    5. А если алгоритм будет понескольку раз проходить один и тот же элемент, то тут вообще хрен знает какое получится быстродействие

    Достаточно аргументов?
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Proteus
    не совсем понял о чём речь.