Создание дерева

Для создания дерева в памяти тоже применяется алгоритм обхода. Первым шагом этого алгоритма является проверка необходимости создания узла.

Если ответ положительный, узел создаётся и в нём заполняются информационные поля. В частности, может быть выполнен шаг разметки. Далее заполняются поля указателей на каждого сына: для получения значения указателя алгоритм запускается рекурсивно. Результат — указатель на вновь созданный узел или нуль, если узел не создан.

Проверка необходимости создания узла может быть выполнена тремя способами:

1. Запрос на ввод с клавиатуры. Приглашение ко вводу может содержать какую-либо информацию о месте предполагаемого узла в дереве. Ожидаемый ответ — «да» или «нет» (1 или 0, Y или N, и т. п.). Вместо ответа «да» можно вводить информацию для размещения в узле, особый ввод, например, пустой, может означать «нет».

2. Чтение очередного элемента заранее заготовленной последовательности из массива, линейного списка или файла. Такая последовательность сама по себе тоже является способом размещения дерева в памяти, а алгоритм ввода просто преобразует её в форму разветвляющегося списка.

3. Обращение к датчику случайных чисел с целью генерации дерева. Датчик должен быть управляемым. Простой датчик с равновероятной выдачей 0 или 1 будет создавать пустые или очень маломощные деревья — из 1, 2, 3 узлов, т. к. вероятность того, что узел будет создан, очень быстро падает с ростом его глубины: для корня она составляет всего 0.5, для сыновей — 0.25 (0.52) и т. д. Нужен датчик, который бы обеспечивал вероятность создания корня близкую к 1 и уменьшал её с ростом глубины узла.

Пример такого датчика:

Y = depth < rand() % 6 + 1,

где depth — глубина узла: для корня она 0, для произвольного узла — на 1 больше, чем у отца. Очевидно, что для корня Y = 1, а для узла на глубине больше 5 — всегда 0.

Функция-член для генерации случайного дерева может выглядеть так:

Node * Tree:: MakeNode(int depth)

{ Node * v = NULL;

int Y = (depth < rand()%6+1) && (num <= 'z');

// Вариант: cout ≪ "Node (" ≪ num ≪ ',' ≪ depth ≪ ")1/0: "; cin ≫ Y;

if (Y) { // создание узла, если Y = 1

v = new Node;

v->d = num++; // разметка в прямом порядке (= «в глубину»)

v->lft = MakeNode(depth+1);

// v->d = num++; //вариант — во внутреннем

v->rgt = MakeNode(depth+1);

// v->d = num++; // вариант — в обратном

}

return v;

}

Эта функция запускается из встраиваемой функции-члена MakeTree(), результат её работы присваивается полю root.

Вместо генерации случайного значения Y можно организовать ввод его с клавиатуры. Соответствующая альтернатива помещена в комментарий.

Функция создаёт дерево прямым обходом по той простой причине, что невозможно создать узел дерева, если не создан его отец. Но вот считать узел «пройдённым» можно когда угодно. Поэтому для разметки узла в алгоритме можно использовать три точки (две из них закомментированы): до обхода поддеревьев, после левого поддерева и перед правым, и по окончании обхода поддеревьев. Нужный вариант разметки можно обеспечить, включив инициализацию в соответствующей точке и выключив — в остальных.

Значение глубины узла depth, необходимое для датчика, известно при входе в функцию и может быть использовано в любом месте. А вот данные, зависящие от поддеревьев: высота узла, количество листьев, количество потомков и т. п., могут быть известны только тогда, когда оба поддерева уже обработаны, т. е. они доступны только при обратном обходе.