Предположим, у вас есть полное двоичное дерево (т.е. каждый внутренний узел имеет ровно двух непустых потомков). Каждый узел содержит ненулевое целое число. Вам дано задание кодировать и декодировать дерево в / из списка целых чисел.
Дерево хранится внутри что-то вроде:
struct node {
int data;
struct node *left, *right;
};
И вам нужно реализовать две функции:
int *encode(struct node *root);
struct node *decode(int *array);
Это зависит от вас, как вы кодируете и декодируете.
Очки за:
- минимальная длина кодирования
- сложность (идеально линейная по количеству узлов)
- оригинальность
Нет баллов за длину исходного кода, и вы не ограничены C.
Пример дерева:
5
/ \
3 2
/ \
2 1
/ \
9 9
code-challenge
tree-traversal
Александр
источник
источник
int *
черный ящик для пользователяОтветы:
~ 1,03 Н
Кажется, что все ответы до сих пор занимают минимум 2 * N * 32-бит для хранения. (За исключением решений на языках, которые допускают целочисленные значения длиннее 32 бит, как, например, решения на Haskell и Ruby - но они по-прежнему будут требовать дополнительных байтов для кодирования всякий раз, когда данные больше 16K.)
Вот решение, которое занимает только N + потолок (N / 32) +1 дюйм хранения. Это приближается к 1,03125 N для больших N и меньше 1,1 N для всех N больше 20.
Идея состоит в том, чтобы сохранить дополнительный бит для каждого узла, где 1 - это hasChildren. Эти биты упакованы в N / 32 слова заранее.
(отличная реализация здесь)
источник
Эта программа на Haskell кодирует дерево из n узлов в n целых числах. Хитрость заключается в том, что он кодирует данные узла в два раза, а затем использует младший бит, чтобы указать, является ли это листовым узлом или внутренним узлом.
Технически,
Parser
монада здесь чрезмерная, так как создан только один парсер,decoder
и я мог бы поместить логику цепочки парсера прямо туда. Но в этом случае декодер очень понятен, и,Parser
несмотря на его небольшой размер, представляет собой разумную простую структуру синтаксического анализа.Запуск этого получает вас:
источник
В С
Кодировать:
Расшифровка:
Основной:
Заметка. Каждый узел кодируется как два целых числа (плюс одно целое для количества узлов).
Таким образом, поставляемое дерево кодируется так:
источник
В Ruby с той же кодировкой, что и у @MtnViewMark :
Стоимость составляет одно целое число на узел (
data << 1 | has_childs
):источник
Дано двоичное дерево с
n
узлами, это кодирует его в список2n + 1
целых чисел. Оба алгоритма кодирования и декодирования имеютO(n)
сложность.Я использую целое число 0 в качестве часового маркера при кодировании, указывая, когда я раскрываю рекурсию. Затем, когда я декодирую, я помещаю создаваемые мной узлы дерева в стек (своего рода) и использую 0 в списке, чтобы отслеживать, куда добавить следующий узел. Я не пробовал, но я уверен, что декодирование сломалось бы, если бы дерево не было завершено.
Сохранено это как
encode.c
потом скомпилировано и выполнено. Эта программа использует предоставленное вами дерево примеров, и я успешно протестировал его на нескольких других.источник
Мой код кодирует дерево в обходе предзаказа, каждый лист в два целых (его данные следуют за 0) и каждый внутренний узел в одном int (за его данными следует левый потомок, затем его правый). Для полного двоичного дерева (как вы его определяете) с n узлами, n должно быть нечетным, и есть (n + 1) / 2 листьев и (n-1) / 2 внутренних узла, так что это 3n / 2 + 1 / 2 целых числа для кодирования.
предупреждение: не проверено, просто набрал его
источник
Вот моя попытка. Он хранит дерево в массиве размером 2 ** глубина + 1. Он используется
a[0]
для хранения размера иa[size]
для хранения индекса первого «пустого узла», с которым он сталкивается при прохождении в глубину. (Пустой узел - это место, где будет храниться дочерний элемент, если у него был родитель). Каждый пустой узел содержит индекс следующего пустого узла, который будет встречен.Эта схема позволяет избежать резервирования битов для обозначения присутствующих потомков, поэтому каждый узел может использовать полный диапазон целых чисел. Также допускаются несбалансированные деревья - у родителя может быть только один ребенок.
выход:
Кодировщик:
Декодер:
(спасибо @daniel sobral за исправление форматирования)
источник
Scala:
Это подход, который использует устаревший синтаксис, но компилируется без ошибок в Scala 2.9.1. Он генерирует дерево и декодирует каждое закодированное дерево в тот же массив, который используется для кодирования. Может быть, я каким-то образом избавился от устаревших предупреждений сегодня.Вау - это было просто. Первая идея сработала сразу.
источник