Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > JavaScript: Общие вопросы > Обход бинарного дерева |
Автор: t77 19.3.2012, 12:52 |
Доброе время суток! Вопрос собственно в том, как на javascript реализовать обход бинарного дерева ? Проходим по нодам дерева и печатаем текст каждого нода... Какие варианты имеются (рекурсия, ООП и т. д.) ? Возможные решения? Спасибо. |
Автор: Stolzen 19.3.2012, 13:02 |
Рекурсия - самый простой способ. Сколько элементов в дереве? Как граф представлен? Если элементов много, то лучше самому реализовать стек (про размер стека в разных браузерах можно почитать http://www.nczonline.net/blog/2009/05/19/javascript-stack-overflow-error/). |
Автор: t77 21.3.2012, 14:58 |
Элементов в дереве может быть много, заранее не известно! Граф представлен следующим образом: Рут(корневой элемент) дерева "А" Его дети: "B", "С", "D Дети элемента "B": "Е", "F", "G" Дети элемента "C": "H", "I", "K" Дети элемента "D": "L", "M", "N" У каждого из детей тоже имеются дети! Ну и так далее... В принципе не важно сколько детей будет у каждого элемента и какого размера будет дерево. Важно пройтись по каждому элементу дерева и распечатать текст(название). |
Автор: Stolzen 22.3.2012, 08:48 | ||
Примерно алгоритм должен быть такой (псевдокод):
П.С. Вы не ответили на вопрос про представление дерева, вы только показали, что, какие данные в нем. Какая структура данных используется для хранения графа? И это не бинарное дерево |
Автор: t77 24.3.2012, 19:34 |
Stolzen , это один из вопросов, которые недавно слышал на собеседовании... Поэтому не представлена структура для хранения графа. А представление дерева было просто нарисовано на листке бумаги, в виде кружочков, соединенными между собой. |