Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > 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
Примерно алгоритм должен быть такой (псевдокод):
Код

function printNode(node) {
    printText(node.getText());
    foreach (child in node.getChildren()) {
        printNode(child);
    }
}


П.С. Вы не ответили на вопрос про представление дерева, вы только показали, что, какие данные в нем. Какая структура данных используется для хранения графа? И это не бинарное дерево

Автор: t77 24.3.2012, 19:34
Stolzen , это один из вопросов, которые недавно слышал на собеседовании...
Поэтому не представлена структура для хранения графа. А представление дерева было просто нарисовано на листке бумаги, в виде кружочков, соединенными между собой.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)