помогите написать для собеседования функцию обхода бинарного дерева:

— слева-направо;
— справа-налево;
— сверху-вниз;
— снизу-вверх.

Здравствуйте, Hard_Club, Вы писали:

H_C>помогите написать для собеседования функцию обхода бинарного дерева:

А работать за тебя кто потом будет?

Здравствуйте, Hard_Club, Вы писали:

H_C>помогите написать для собеседования функцию обхода бинарного дерева:

H_C>- слева-направо;
H_C>- справа-налево;
H_C>- сверху-вниз;
H_C>- снизу-вверх.


А что, собственно, представляет трудность?

Здравствуйте, Hard_Club, Вы писали:

H_C>помогите написать для собеседования функцию обхода бинарного дерева:

H_C>- слева-направо;
H_C>- справа-налево;
H_C>- сверху-вниз;
H_C>- снизу-вверх.

1. Пишем заголовок — сверху-вниз.
2. Пишем проход корня.
3. Пишем проход левого поддерева
4. Пишем проход правого поддерева

Для получения остальных вариантов тасуем п. 2-4 в произвольном порядке, после чего выясняем, что же у нас получилось

Здравствуйте, Hard_Club, Вы писали:

H_C>помогите написать для собеседования функцию обхода бинарного дерева:

H_C>- слева-направо;
H_C>- справа-налево;
H_C>- сверху-вниз;
H_C>- снизу-вверх.

Слева-направо:

PAGE ,132
STACK SEGMENT PARA STACK ‘STACK’
DB 64 DUP(’STACK ‘)
STACK ENDS
DSEG SEGMENT PARA PUBLIC ‘DATA’
SOURCE DB 10,20,30,40
SUBTTL а
PAGE
CSEG SEGMENT PARA PUBLIC ‘CODE’
OUR_PROG PROC FAR
ASSUME CS:CSEG,DS:DSEG,SS:STACK
PUSH DS
MOV АХ,0
PUSH AX
MOV AX,DSEG
MOV DS,АХ
MOV AL,SOURCE
MOV DEST+3,AL
MOV AL,SOURCE+1
MOV DEST+2,AL
MOV AL,SOURCE+2
MOV DEST+1,AL
MOV AL,SOURCE+3
MOV DEST,AL
RET
OUR_PROG ENDP
CSEG ENDS
END OUR_PROG

Справа-налево и сверху-вниз, думаю, по аналогии сообразите?

Ой, не заметил, что надо на c++. Тогда в начало надо поставить "asm {" и в конец "}"

Здравствуйте, Hard_Club, Вы писали:

H_C>помогите написать для собеседования функцию обхода бинарного дерева:

Эхъ, молодёжжж...

H_C>- слева-направо;
H_C>- справа-налево;
H_C>- сверху-вниз;
H_C>- снизу-вверх.

Поперечные, нисходящий и восходящий порядки обхода.

Подсказка:
На самом деле, они делаются совершенно одинаковым способом!
Попробуй сам сообразить, что же такого одинакового...

	отгадка!
	http://files.rsdn.ru/4783/traverse-bin-trees.gif

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Hard_Club, Вы писали:

H_C>>помогите написать для собеседования функцию обхода бинарного дерева:

К>Эхъ, молодёжжж...
эх, теоретики... пусть у нас есть struct TREE, пусть у нас есть массив этих структур, тогда для для поиска элемента мы трактуем его как дерево, а если нам нужно вывести все элементы (обойти дерево) — трактуем как массив и обход записывается в одну строку: for(a=0;a<n;a++) if (tree[a].valid) printf("%x\n", tree[a].val);

тут же способ быстрого удаления элементов из дерева. tree[idx].valid = 0. если операций удаления немного, то это хороший способ правда есть риск, что после множества удалений под конец дерево на 99% будет состоять из удаленных элементов, но на этот случай пишем сборщик мусора, удаляющий уже по науке.

ЗЫ, понятно, что задача предполагает обход именно по науке, но если дерево не задано явно, то можно и через for его обойти как массив, хотя зачтут ли такое решение -- вот тут я не знаю.

Здравствуйте, мыщъх, Вы писали:

К>>Эхъ, молодёжжж...
М>эх, теоретики... пусть у нас есть struct TREE, пусть у нас есть массив этих структур, тогда для для поиска элемента мы трактуем его как дерево, а если нам нужно вывести все элементы (обойти дерево) — трактуем как массив и обход записывается в одну строку: for(a=0;a<n;a++) if (tree[a].valid) printf("%x\n", tree[a].val);

Эх, практики... Ну и какой будет порядок обхода этого дерева?
Вот, например, двоичная куча, классически размещается в массиве. Линейному обходу массива соответствует обход дерева вширь (нулевой ярус, первый ярус, второй ярус и т.д.)
А сделать любой обход вглубь (поперечный, восходящий или нисходящий) — тут уже помощник нужен.

Кстати, этюд.
Пусть куча размером N размещена в массиве arr[0..N-1].
У узла k дочерние узлы — 2k и 2k+1.
Написать функцию j(i), соответствующую одному из обходов вглубь: т.е. пробегаем по arr[j(0)], arr[j(1)], ...
— аналитическое выражение
— итерационное, — j(i) как функция от j(i-1)
Рассмотреть варианты, когда дерево насыщено (N=2^h-1) и ненасыщено.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, мыщъх, Вы писали:

К>>>Эхъ, молодёжжж...
М>>эх, теоретики... пусть у нас есть struct TREE, пусть у нас есть массив этих структур, тогда для для поиска элемента мы трактуем его как дерево, а если нам нужно вывести все элементы (обойти дерево) — трактуем как массив и обход записывается в одну строку: for(a=0;a<n;a++) if (tree[a].valid) printf("%x\n", tree[a].val);

К>Эх, практики... Ну и какой будет порядок обхода этого дерева?
не понял. O(N). куда уж быстрее? (если под обходом понимается посещение всех узлов дерева).

понятно, что задача обхода поддерева так уже не решается (в общем случае).

К>Кстати, этюд.
К>Пусть куча размером N размещена в массиве arr[0..N-1].
К>У узла k дочерние узлы — 2k и 2k+1.
...
К>Рассмотреть варианты, когда дерево насыщено (N=2^h-1) и ненасыщено.
стоп! давайте все-таки ближе к практике. у математиков время доступа к любому элементу массива -- постоянно. на практике чтение от 0 до N-1 может быть в разы быстрее, чем чтение в разброс. а может отличаться и больше чем на два порядка, особенно если мы выпадаем в своп.

последовательное чтение массива даже в случае если он заполнен от силы на 10% не обязательно выполняется за большее время, чем обход дерева в порядке родства узлов. а потому с инженерной точки зрения абстрактное математическое решение не предсталяет никакого интереса и этот интерес тем меньше, чем больше дерево. для дерева с размеров в несколько гигов смысл насыщенности теряется. все равно читаемы мы сектор (в лучшем случае!). даже если в этом секторе у нас всего несколько узлов, а остальное -- пустота, время обработки пустоты — навряд ли ухудшит производительность. дерево может быть насыщено менее чем на 1%, но обрабатываться за тоже время, что и 100% насыщенное.

А возможно ли сделать обратный линейный обход без дополнительной памяти?
Ну, то есть, со стеком-то легко, а вот без него как? С нахрапу как-то ничего не приходит...

Здравствуйте, Кодт, Вы писали:

> У узла k дочерние узлы — 2k и 2k+1.
бред (с)
1) если у нас есть функа трансляции узлов и эта функа задана заранее — зачем вообще нам такое дерево? дерево же вырождается...
2) для узла 0 получаем дочерей 0 и 1. мабуть вы хотели сказать: 3k+1 и 3k+2 ?

3) вообще идея массива в том, что в жизни у дерева есть узел q, у него дочки w и e, причем, q, w и e физически расположнены очень далеко друг от друга. (в начале, середине и конце файла, в котором хранится дерево). со всеми отсюда вытекающими...

4) еще про обход дерева -- как насчет (не)выделения доп. памяти, запрета на рекурскию и т.д.?

сравнивать одно решение с другим только через сложность -- не самая лучшая идея, т.к. как уже говорилось выше даже если k << n (<< — сильно меньше), то не нужно забывать о том, что последовательное чтение сильно быстрее чтения вразборс (и оно _точно_ сильно быстрее). потому в задаче о ненасыщенность придется юлить.

как уже писалось, если минимальная единица чтения порции информации содержит хотя бы один элемент, то в рамках этой минимальной единицы -- время обработки это константа. выиграть при "умном" обходе можно только когда в массиве есть единцы чтения, в которых вообще нет ни одного элемента, но тогда можно (и не так уж сложно) создать карту затяных областей или использовать массив списка массивов. и массив списка массивов это все равно проще обхода по "науке"

Здравствуйте, silent_bob, Вы писали:

_>А возможно ли сделать обратный линейный обход без дополнительной памяти?
_>Ну, то есть, со стеком-то легко, а вот без него как? С нахрапу как-то ничего не приходит...
вот-вот. и учитывая специфику ЭВМ давайте добавим к этюду: без выделения доп. памяти и посещая каждый узел не более одного раза.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Hard_Club, Вы писали:

H_C>>помогите написать для собеседования функцию обхода бинарного дерева:

К>Эхъ, молодёжжж...

H_C>>- слева-направо;
H_C>>- справа-налево;
H_C>>- сверху-вниз;
H_C>>- снизу-вверх.

К>Поперечные, нисходящий и восходящий порядки обхода.

К>Подсказка:
К>На самом деле, они делаются совершенно одинаковым способом!
К>Попробуй сам сообразить, что же такого одинакового...

К>

	отгадка!
	К>http://files.rsdn.ru/4783/traverse-bin-trees.gif

я почему-то думал, что обходы бывают в ширь и в глубину.

Здравствуйте, Hard_Club, Вы писали:

H_C>я почему-то думал, что обходы бывают в ширь и в глубину.

Поперечный, восходящий и нисходящий — это всё обходы в глубину.

down(node)   =                                    visit(node.data), down(node.left), down(node.right)
up(nown)     = up(node.left),     up(node.right), visit(node.data)
across(node) = across(node.left),                 visit(node.data),                  across(node.right)

А в ширину — это поярусно (корень; все дети; все внуки; все правнуки; и т.д.)
Тут уже локально одним узлом не отделаешься.

Здравствуйте, мыщъх, Вы писали:

К>>Эх, практики... Ну и какой будет порядок обхода этого дерева?
М>не понял. O(N). куда уж быстрее? (если под обходом понимается посещение всех узлов дерева).

Ага, у любой задачи есть решение — красивое (for(i=0;i!=n;++i)), быстрое (O(n))... и неправильное.
Топикстартеру нужно сделать обходы вглубь (поперёк, поперёк, нисходящий и восходящий).
А ты предлагаешь — как попало, в порядке размещения узлов в массиве.

Вот тебе два примера.
1) я уже назвал, пирамида (которая из heap_sort)
2) отсортированный массив, порядок совпадает с поперечным обходом любого двоичного дерева поиска
Теперь сделай на отсортированном массиве восходящий или нисходящий обход. (Какого именно дерева? Их там C(n) штук).

Здравствуйте, мыщъх, Вы писали:

>> У узла k дочерние узлы — 2k и 2k+1.
М>бред (с)
М>1) если у нас есть функа трансляции узлов и эта функа задана заранее — зачем вообще нам такое дерево? дерево же вырождается...

Но это же всё равно дерево. В список не вырожденное.

М>2) для узла 0 получаем дочерей 0 и 1. мабуть вы хотели сказать: 3k+1 и 3k+2 ?

Упс! Замечтался о своём, о девичьем... 2k+1, 2k+2

    ____0____
  _1_       _2_
 3   4     5   6
7 8 9 10 11 × × ×   недостроенная пирамида

М>4) еще про обход дерева -- как насчет (не)выделения доп. памяти, запрета на рекурскию и т.д.?

Это всё время-деньги.
Например, для обхода произвольного дерева вширь нам потребуется или очередь узлов, ожидающих посещения, или мы можем совершить H+1 обходов дерева вглубь, спускаясь каждый раз на ярус h=0..H, где H — высота дерева.
То есть, или линейная память, или квадратное время.

М>сравнивать одно решение с другим только через сложность -- не самая лучшая идея
Заметь, это была твоя идея.

Здравствуйте, silent_bob, Вы писали:

_>А возможно ли сделать обратный линейный обход без дополнительной памяти?
_>Ну, то есть, со стеком-то легко, а вот без него как? С нахрапу как-то ничего не приходит...

Если дерево двусвязное, т.е. есть функция parent(node) — например, в виде указателя на родительский узел, — то безо всякого стека и нахрапа.
Немножко покурить на мой рисунок, и всё станет ясно.
И заодно станет ясно, сколько времени требуется на полный обход любого двоичного дерева, вне зависимости от его сбалансированности.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, мыщъх, Вы писали:

К>Ага, у любой задачи есть решение — красивое (for(i=0;i!=n;++i)), быстрое (O(n))... и неправильное.
К>Топикстартеру нужно сделать обходы вглубь (поперёк, поперёк, нисходящий и восходящий).
К>А ты предлагаешь — как попало, в порядке размещения узлов в массиве.
я ж сразу сказал, что юмора не поймут и не зачтут

Здравствуйте, Hard_Club, Вы писали:

H_C>помогите написать для собеседования функцию обхода бинарного дерева:

H_C>- слева-направо;
H_C>- справа-налево;
H_C>- сверху-вниз;
H_C>- снизу-вверх.

К сожалению знаю только обход из центра в стороны .