Как найти горизонтальное расстояние между двумя узлами на одном уровне в двоичном дереве?

Question

Для двоичного дерева: Бинарное дерево высотой 3

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

          f
      /         \
     g           h      
    /  \        /  \        
  a                d    

между узлами a и d горизонтальное расстояние равно 2.

Редактировать:

Обратите внимание, что расстояние между a и d рассчитывается на том же уровне, не включая родительские или дочерние узлы a или d, но только отсутствующие узлына том же уровне.таким образом, расстояние между a и d будет a> (x> y)> d, где в x и y - отсутствующие дочерние узлы узлов g и h соответственно.Следовательно, не считая целевые узлы a и d, горизонтальное расстояние будет 2

.

Answer 1

Думайте об этом так:

      a
    /   \
   b      c
  /  \   / \
 e    f g   h

Теперь вы хотите определить горизонтальное расстояние между узлами на одном уровне.Например: F и G.Вот пошаговый подход:

1. Выполните обход порядка двоичного дерева и сохраните значения в массиве.
2. В результате получается массив с элементами в качестве узлазначения.
3. Обход элементов массива.Когда вы встречаете f (начальный узел), установите счетчик на 0.
4. Продолжайте обход массива и проверьте, что:
   1. Если встречается g (конечный узел), остановите
   2. Если счетчик установлен, а конечный узел не обнаружен, обновите значение счетчика на 1.
5. Наконец, выведите значениесчетчика.

Обновление : Как указано в anand_v.singh, если дерево может быть не полностью заполнено на всех уровнях, оно может дать неправильные результаты.
Чтобы преодолеть эту проблему, будет определен дополнительный параметр tree_height.Предположим, что высота дерева равна 3, тогда массив будет содержать не более 2 ^tree_height -1 элементов, причем все они инициализируются значением, которое не равно значению каких-либо узлов дерева.Теперь вы можете использовать что-то вроде представления массива двоичной кучи, чтобы поместить значения узлов в массив под их соответствующими индексами.Затем следуйте вышеупомянутой процедуре, чтобы получить результаты.