|
(пишу на С++, поэтому сори за неточности)
1) Создается структура, либо класс, описывающая один узел.
2) Пишутся функции для работы с деревом. При этом каждый узел есть поддерево и может ничем не отличаться(кроме содержимого) от главного дерева. Для варианта без класса придется использовать глобальную переменную указатель на вершину дерева, либо всюду передавать локальную.
Отступление:
У каждого узла есть не >2 потомков, а он соответственно является их родителем.
Также иногда встречается название "дядя". Конечные узлы без потомков называют "внешними" или "листами" их антиподы - "внутренние" узлы.
Чтобы запихать дерево в массив его вершины нумеруются начиная с верха.
Номера потомков - 2*N и 2*N+1, где N - ноиер текущего узла. Вроде этого:
1
/ \
2 3
/ \ / \
4 5 6 7
Для бинарного дерева проще всего написать рекурсивные функции. Как правило такая функция обрабатывает значение в текущем узле и вызвает себя для 2 потомков от очередности этих трех действий зависит тип обхода дерева.
Если в силу некоторых причин рекурсивные функции писать нельзя/неоптимально пишутся итеративные, но тогда придется самому в цикле бегать по всему дереву и сохранять пройденный путь(либо завести указатель на родителя).
|