Найдите первое значение null в двоичном дереве с ограниченной памятью

Question

У меня есть двоичное дерево, где каждый узел может иметь значение.

Я хочу найти узел в дереве, который имеет значение null и находится ближе всего к корню.Если есть два узла с одинаковым расстоянием от корня, подойдет любой из них.Мне нужно свести к минимуму количество обращений на чтение к двоичному дереву.Предположим, что рабочая память ограничена всего k узлами.

DFS на глубину k является исчерпывающей, но я не найду ближайший узел, если сначала не пробегусь по всему дереву.BFS найдет ближайший, но это может привести к сбою, потому что DFS может найти более глубокие нули с той же памятью.

Я бы хотел иметь наименьшее количество обращений для чтения к дереву и найти ближайший нулевой узел.

(В конечном счете мне тоже нужно будет реализовать это в n-образных деревьях, так что общее решение было бы хорошим.Нет доступа на запись к дереву, просто читайте.)

Answer 1

Возможно, вы захотите взглянуть на Итеративный поиск с углублением в глубину.Он автоматически найдет ближайший узел, но сможет достичь той же глубины, что и DFS.Однако он будет использовать больше возможностей доступа для чтения.

Вы также можете начать с BFS, и если вы не найдете null с разрешенной памятью, запустите DFS.

Answer 2

Я бы реализовал DFS с помощью простой обрезки дерева.Таким образом, это неправда, что вам нужно запускать все дерево целиком.

Например, если вы расположили нулевое значение на высоте h, вы можете пропустить узлы, которые находятся в том же или более глубоком положении.

Answer 3

Если вы не можете изменить структуру данных, то вам придется сначала прочитать каждый узел по ширине.

Если вы можете изменить структуру данных, то каждый узел мог бы записывать относительную глубину первого нулевого дочернего узла.(Каждый должен выработать на основе эквивалентных значений своих детей).

Тогда вы знаете, за какой строкой в дереве следует следить при поиске самого раннего null.

Answer 4

Есть простой способ, если вы хотите сохранить свое дерево в виде массива.Вместо того, чтобы каждый узел имел указатели на своих левых и правых дочерних элементов, дочерними элементами узла n являются 2n + 1 и 2n + 2 в массиве.(И родительский узел n равен (n-1)/2, если n != 0.)

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

Простая линейная итерация по массиву эквивалентна BFS, но с требованиями к пространству O (1).

Это может быть легко распространено на n-арные деревья.например, в троичном дереве левый потомок равен 3n + 1, центральный равен 3n + 2, правый равен 3n + 3, а родительский равен (n-1)/3, если n !=0.