Лекция: Алгоритм 3.1 нумерации узлов двоичного дерева в соответствии с внутренним

Порядком.

Вход. Двоичное дерево, представленное массивами Leftson и Rightson.

Выход. Массив, названный Number (Номер), такой, что Number[i] – номер узла i во внутреннем порядке.

Метод. Кроме массивов Leftson, Rightson и Number, алгоритм использует глобальную переменную counter (Счет), значение которой — номер очередного узла в соответствии с внутренним порядком. Начальным значением counter является 1. Параметр node (Узел) вначале равен корню. При прохождении дерева в стеке Vertex запоминаются все узлы, которые ещё не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла v к его левому сыну узел v запоминается в стеке. После нахождения левого поддерева для v узел v нумеруется и выталкивается из стека. Затем нумеруется правое поддерево для v.

При переходе из v к его правому сыну узел v не помещается в стек, поскольку после нумерации правого поддерева не нужно возвращаться в v. Более того, нужно вернуться к тому предку узла v, который еще не занумерован (т.е. к ближайшему предку w узла v, такому, что v лежит в левом поддереве для w). После чего процедура повторяется для выбранного правого сына текущего узла.

Программа 3.1 нумерации узлов двоичного дерева в соответствии с внутренним