Бинарное дерево с левым дочерним элементом и правым родственным элементом
-
Представление многоуровневых деревьев в бинарных
- Каждая многоуровневая древовидная структура может быть представлена в виде бинарного дерева.
- Бинарное дерево имеет различные названия, включая представление дочерних элементов, двоичное дерево с левым дочерним элементом, с правым дочерним элементом, дерево с двойной цепью или цепочка «сын-наследник».
-
Структура бинарного дерева
- Каждый узел в бинарном дереве имеет два указателя: на первый дочерний узел и на следующего родственника.
- Дочерние элементы узла образуют односвязный список.
-
Преобразование из k-арного дерева в бинарное
- Процесс преобразования называется преобразованием Кнута.
- Корень исходного дерева становится корнем бинарного дерева.
- Левый дочерний элемент каждого узла становится левым дочерним элементом в бинарном дереве, а ближайший родственник справа становится правым дочерним элементом.
-
История и описание
- Деревья с двойной цепью были описаны Эдвардом Х. Сассенгутом в 1963 году.
- При преобразовании каждый узел связывается и выравнивается по левому дочернему элементу, а следующий ближайший узел является родственным.
-
Примеры и использование
- Представление LCRS занимает больше места, но поиск дочерних узлов по индексу медленнее.
- Представление LCRS предпочтительнее при больших многоходовых деревьях или в специализированных структурах данных.
- В структурах данных кучи операции удаления корня и соединения деревьев эффективны в представлении LCRS.