Вид бинарного дерева с 45 градусов - PullRequest
Новая
       30

Вид бинарного дерева с 45 градусов

0 голосов
/ 04 мая 2018

Так что я не прошу диагональный вид дерева, которое, к счастью, я уже знаю. Я спрашиваю, вижу ли я дерево под углом 45 градусов, должны быть видны только несколько узлов. Так что есть плоскость, которая под углом 45 градусов от оси х. поэтому нам нужно распечатать все узлы, которые видны с этой плоскости.

Например: 

            1
          /    \
          2      3
        /  \    /  \
       4   5   6    7

Так что, если я посмотрю с этой плоскости, я увижу только узлы [4, 6, 7], поскольку 5 и 6 перекрывают друг друга. Если я добавлю другой узел в 6, теперь он будет скрыт 7. Как это сделать? Я искал в интернете, но не смог найти ответ.

Спасибо!

1 Ответ

0 голосов
/ 04 мая 2018

Я даю вам абстрактный ответ, поскольку вопрос не зависит от языка.

Проблема с регистрацией таких деревьев заключается в использовании рекурсии.

Я имею в виду, что обход идет вниз по узлам и вверх по узлам.

Что если бы вы написали помощник высоты, который бы возвращал глубину текущего узла.

Для каждого уровня глубины вы помещаете значение в массив.

Затем запишите значения массива.

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

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

int total_depth = tree.getTotalHeight();
int arr[total_depth] = {};
for(int i = total_depth; i--;){
   // there is a formula for the max number of nodes at a given depth of a binary tree
   arr[i] = int arr[maximum_nodes_at_depth]
}
tree.inorderTraverse(function(node){
    int depth = node.getHeightHelper();
    // check if item is null
    if( node!=nullptr && node.Item != NULL)
    {
        arr[depth].push(node.Item)
    }
    else
    {
        arr[depth].push(NULL)    
    }
})

Так что теперь вам нужно будет рассчитать размер вашего дерева, а затем динамически вычислить, сколько пробелов должно предшествовать каждому узлу. Чем ниже глубина, тем больше префиксов для ее центрирования.

Я извиняюсь, но псевдокод представляет собой смесь синтаксиса javascript и c ++ .... что никогда не должно происходить lol

...