1
полного бинарного дерева может быть эффективно реализован в виде массива, в котором узел по индексу я имею ребенок в индексах 2i и 2i +- и родительский по индексу пола (я/2), с one-based индексирование.Как доказать преобразование из конкурирующего двоичного дерева в массив?
Если дочерний индекс больше числа узлов, то ребенок не существует.
Я вижу эти конверсии каждый, но есть нет формального доказательства их, можете ли вы дать строгие доказательства или ссылку на него, спасибо!
Красивое доказательство! Я поймал ключевой момент: количество узлов на полном уровне ** L ** почти ** 2 ** раз число узлов на всех его предыдущих уровнях ** от 0 до L-1 **, поэтому мы имеем ** ** ** в выражении ** 2 * i + 2 **. –