Построение двоичного дерева на основе модифицированной схемы хранения…
3
При хранении дерева каждый его узел представляется в виде
структуры с полями, в которых хранятся ссылки на другие элементы
дерева. При описании двоичных деревьев с порядком на «детях» та-
ких полей обычно три: ссылка на «родителя» (parent), ссылка на
«правого ребенка» («right child») и ссылка на «левого ребенка» («left
child»). В некоторых случаях ссылка на «родителя» может отсутство-
вать, но тогда алгоритмы обработки данного дерева значительно
усложняются, а некоторые вообще не представляется возможным ре-
ализовать для данного дерева. Поэтому далее будет разобрано дере-
во, элементы которого представлены структурой, содержащей в себе
три рассмотренных выше поля.
Рекурсивный алгоритм создания дерева с числом элементов
n
можно описать следующим образом (рис. 4) [2]:
struct Tree
{
int data;
Tree *leftChild;
Tree *rightChild;
};
Tree *CreateTree(int n)
{
int nl, nr;
Tree *current;
if (n == 0)
current = NULL;
else
{
current = new Tree;
nl = n/2; nr = n — nl — 1;
cout << "Input element of a tree: ";
cin >> current->data;
current->leftChild = CreateTree(nl);
current->rightChild = CreateTree(nr);
}
return current;
}
Недостатком данного алгоритма является необходимость заранее
знать число элементов создаваемого дерева. Кроме того, сразу нельзя
представить расположение элементов в древовидной структуре.
Теперь рассмотрим LCRS-схему хранения двоичного дерева. Она
предполагает наличие у каждого узла дерева трех ссылок: на «роди-
теля», на «левого ребенка» и на «правого соседа». Алгоритм создания
дерева предполагает не создание результирующего дерева вызовом
одной функции, а постепенное добавление к существующему дереву
очередного узла [3].
