Напишите самую короткую программу для вычисления высоты двоичного дерева

18

Высота бинарного дерева - это расстояние от корневого узла до дочернего узла, который находится дальше всего от корня.

Ниже приведен пример:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Высота бинарного дерева: 4

Определение двоичного дерева

Дерево - это объект, который содержит целочисленное значение со знаком и два других дерева или указатели на них.

Структура структуры двоичного дерева выглядит примерно так:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;

Соревнование:

вход

Корень бинарного дерева

Выход

Число, представляющее высоту двоичного дерева

Предполагая, что вам дан корень двоичного дерева в качестве входных данных, напишите самую короткую программу, которая вычисляет высоту двоичного дерева и возвращает высоту. Программа с наименьшим количеством байтов (учет пробелов) выигрывает.

Т. Салим
источник
4
Что делают языки без указателей?
Джонатан Аллан
4
... но тогда у моего объекта дерева может быть свойство, скажем h. Возможно, для этой задачи лучше определить конкретную структуру, состоящую только из списков.
Джонатан Аллан
11
@ T.Salim В будущем, пожалуйста, сначала рассмотрите возможность размещения в песочнице .
wizzwizz4
1
Итак, является ли допустимое представление списком длины 3, в [root_value, left_node, right_node]котором допустимо каждое из двоичных деревьев, left_nodeа right_nodeтакже? Это будет тривиально на многих языках, но может быть забавным на некоторых других.
Джонатан Аллан
3
Можете ли вы отредактировать вопрос, включив в него то, что составляет действительную двоичную структуру? Возможно определение как a tree is an object that contains a value and either two other trees or pointers to them. Определение, включающее языки без объектов, также было бы неплохо.
Джо Кинг

Ответы:

11

Желе , 3 байта

ŒḊ’

Монадическая ссылка, принимающая список, представляющий дерево:, [root_value, left_tree, right_tree]где каждая из left_treeи right_treeявляется похожими структурами (пустые, если необходимо), которая возвращает высоту.

Попробуйте онлайн!

Как?

Довольно тривиально в желе:

ŒḊ’ - Link: list, as described above
ŒḊ  - depth
  ’ - decremented (since leaves are `[value, [], []]`)
Джонатан Аллан
источник
Джонатон Аллен, это интересный язык, который вы используете. Как новичок, можете ли вы предоставить ссылку или ссылку на сайт, который обучает людей, как использовать Jelly?
Т. Салим
4
Нажмите на ссылку в шапке - это язык игры в гольф, разработанный Денисом , одним из модераторов сайта.
Джонатан Аллан
2
Интересно , как спорное было бы представлять лист , как xвместо того , чтобы [x, [], []]...
Эрик Outgolfer
@EriktheOutgolfer Чтобы сохранить природу вопроса «указатель» и «структура», я думаю, что каждый узел должен иметь одинаковую форму.
Джонатан Аллан
10

Python 2 ,  35  33 байта

Спасибо Арно за то, что он заметил недосмотр и спасение 4.

f=lambda a:a>[]and-~max(map(f,a))

Рекурсивная функция, принимающая список, представляющий дерево:, [root_value, left_tree, right_tree]где каждая из left_treeи right_treeявляется похожей структурой (пустой, если необходимо), которая возвращает высоту.

Попробуйте онлайн!

Обратите внимание, что []вернется False, но в Python False==0.

Джонатан Аллан
источник
Один и тот же человек может дать два разных ответа на один и тот же вопрос?
Т. Салим
6
Да, конечно, гольф - это соревнование на уровне языка. Даже вторая запись на том же языке иногда приемлема, если подход очень отличается.
Джонатан Аллан
@ Arnauld Думаю, так (я предположил, что нецелые числа могут присутствовать по какой-то причине)
Джонатан Аллан
6

Haskell, 33 байта

h L=0 
h(N l r _)=1+max(h l)(h r)

Использование пользовательского типа дерева data T = L | N T T Int, который является эквивалентом языка Haskell структуры C, указанной в задании.

Попробуйте онлайн!

Ними
источник
6

Perl 6 , 25 байт

{($_,{.[*;*]}...*eqv*)-2}

Ввод 3-элементный список (l, r, v). Пустое дерево - это пустой список.

Попробуйте онлайн!

объяснение

{                       }  # Anonymous block
    ,        ...  # Sequence constructor
  $_  # Start with input
     {.[*;*]}  # Compute next element by flattening one level
               # Sadly *[*;*] doesn't work for some reason
                *eqv*  # Until elements doesn't change
 (                   )-2  # Size of sequence minus 2

Старое решение, 30 байт

{+$_&&1+max map &?BLOCK,.[^2]}

Попробуйте онлайн!

nwellnhof
источник
&?BLOCKТрюк интересно , но это несколько байт короче , чтобы назначить блок $!
Джо Кинг
@ Шучу, я не знаю. Хранение решения проблемы в изменчивом глобальном мире, как $!или $/для меня, как мошенничество.
nwellnhof
(Ab) с использованием переменных, таких как $! и $ / - довольно стандартная практика для игры в гольф P6.
user0721090601
6

05AB1E , 11 7 5 байт

Δ€`}N

-4 байта благодаря @ExpiredData .
-2 байта благодаря @Grimy .

Формат ввода аналогичен ответу Jelly: список, представляющий дерево:, [root_value, left_tree, right_tree]где каждая из left_treeи right_treeпредставляет собой схожие структуры (необязательно пустые). Т.е. [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]представляет дерево из описания вызова.

Попробуйте онлайн или проверьте еще несколько тестов .

Объяснение:

Δ     # Loop until the (implicit) input-list no longer changes:
  €`  #  Flatten the list one level
}N    # After the loop: push the 0-based index of the loop we just finished
      # (which is output implicitly as result)

Обратите внимание, что хотя 05AB1E основано на 0, цикл изменений Δприводит к корректности выходного индекса, поскольку ему требуется дополнительная итерация для проверки того, что он больше не изменяется.

Кевин Круйссен
источник
1
7 байт?
Просроченные данные
@ExpiredData Ах, конечно .. Спасибо! :)
Кевин Круйссен
1
5 байтов
Grimmy
@ Грими Я думал, что использование индекса вне цикла работает только в устаревшем коде ..: S Спасибо!
Кевин Круйссен
5

JavaScript (ES6),  35  33 байта

Структура ввода: [[left_node], [right_node], value]

f=([a,b])=>a?1+f(f(a)>f(b)?a:b):0

Попробуйте онлайн!

комментарии

f =                       // f is a recursive function taking
([a, b]) =>               // a node of the tree split into
                          // a[] = left child, b[] = right child (the value is ignored)
  a ?                     // if a[] is defined:
    1 +                   //   increment the final result for this branch
    f(                    //   and add:
      f(a) > f(b) ? a : b //     f(a) if f(a) > f(b) or f(b) otherwise
    )                     //
  :                       // else:
    0                     //   stop recursion and return 0
Arnauld
источник
Похоже, вы можете сохранить байт с a&&-~.
Лохматый
1
@ Shaggy Это привело бы к сравнению с неопределенным .
Арно
4

C, 43 байта

h(T*r){r=r?1+(int)fmax(h(r->l),h(r->r)):0;}

Структура бинарного дерева следующая:

typedef struct tree
{
  struct tree * l;

  struct tree * r;

  int v;

} tree;
Т. Салим
источник
2
55 байт Попробуйте онлайн! Некоторые C-специфические трюки в гольф здесь!
ErikF
1
@ErikF Или 45 байтов
Арно
2
43 байта
nwellnhof
3
Если ваша заявка основана на флагах, не могли бы вы добавить их в заголовок вашей заявки?
Джо Кинг
1
Опираясь на @nwellnhof 42 байта
потолок кошка
4

JavaScript (Node.js) , 32 байта

f=a=>/,,/.test(a)&&f(a.flat())+1

Попробуйте онлайн!

Используя имя flatвместо flattenилиsmoosh является отличной идеей для кода гольф.

Используется []для нулевого узла в дереве и [left, right, value]для узлов. valueздесь целое число

ТТГ
источник
3

Haskell, 28 байт

Используя следующее определение данных:

data T a = (:&) a [T a]

Высота составляет:

h(_:&x)=foldr(max.succ.h)0 x
Майкл Кляйн
источник
2

Схема, 72 байта

(define(f h)(if(null? h)0(+ 1(max(f(car(cdr h)))(f(car(cdr(cdr h))))))))

Более читаемая версия:

(define (f h)
   (if (null? h)
      0
      (+ 1 
         (max
             (f (car (cdr h)))
             (f (car (cdr (cdr h))))
         )
      )
   )
)

Использование списков формы (данные, слева, справа) для представления дерева. Например

   1
  / \
  2  3
 /\
 4 5

is represented as: (1 (2 (4 () ()) (5 () ())) (3 () ())

(1
   (2
      (4 () ())
```   (5 () ())
   (3 () ())
)

Попробуйте онлайн!

Захари Хлопок
источник
2

R , 51 байт

function(L){while(is.list(L<-unlist(L,F)))T=T+1;+T}

Попробуйте онлайн!

  • Входные данные: вложенный список в формате:list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • Алгоритм: итеративно выравнивает дерево на один уровень, пока оно не станет плоским вектором: количество итераций соответствует максимальной глубине.

Вдохновленный решением @KevinCruijssen


Рекурсивная альтернатива:

R , 64 байта

`~`=function(L,d=0)'if'(is.list(L),max(L[[2]]~d+1,L[[3]]~d+1),d)

Попробуйте онлайн!

Переопределяет функцию / оператор, '~'позволяя вычислить максимальную глубину дерева, хранящегося в структуре списка.

Структура списка дерева имеет формат: list(ROOT_ELEMENT, LEFT_TREE, RIGHT_TREE)

  • -2 благодаря @Giuseppe
digEmAll
источник
почему вы используете, d=1а затем d-1в конце? Не могли бы вы начать с 0?
Джузеппе
Кроме того, я переключился >на ~ здесь , так что тестовые примеры легче ввести
Giuseppe
@Giuseppe: конечно ... мне не хватало очевидного dig
digEmAll
1

К (нгн / к) , 4 байта

Решение:

#,/\

Попробуйте онлайн!

Объяснение:

Я думаю, что, возможно, упустил момент.

Представляя дерево в виде списка из 3 элементов (parent-node; left-child; right-child), пример может быть представлен как

(2;
  (7;
    (,2);
    (6;
      (,5);
      (,11)
    )
  );
  (5;
    ();
    (9;
      (,4);
      ()
    )
  )
)

или: (2;(7;(,2);(6;(,5);(,11)));(5;();(9;(,4);()))).

Таким образом, решение состоит в том, чтобы итеративно сгладить и посчитать итерации:

#,/\ / the solution
   \ / iterate
 ,/  / flatten
#    / count
streetster
источник
0

Древесный уголь , 29 байт

⊞θ⁰⊞υθFυ«≔⊕⊟ιθFΦι∧κλ⊞υ⊞Oκθ»Iθ

Попробуйте онлайн! Ссылка на подробную версию кода. Временно изменяет дерево во время обработки. Объяснение:

⊞θ⁰

Нажмите ноль в корневой узел.

⊞υθ

Нажмите корневой узел в список всех узлов.

Fυ«

Выполните поиск дерева в ширину.

≔⊕⊟ιθ

Получите глубину этого узла.

FΦι∧κλ

Цикл по любым дочерним узлам.

⊞υ⊞Oκθ

Сообщите дочернему узлу глубину его родителя и поместите его в список всех узлов.

»Iθ

Когда все узлы пройдены, выведите глубину последнего узла. Поскольку обход был в ширину, это будет высота дерева.

Нил
источник
0

Stax , 5 байт

▐▌µ╡⌂

Запустите и отладьте его

Stax не имеет ни указателей, ни нулевых значений, поэтому я представляю ввод как [2,[7,[2,[],[]],[6,[5,[],[]],[11,[],[]]]],[5,[],[9,[4,[],[]],[]]]]. Может быть, это несправедливое преимущество, но это было самое близкое, что я мог получить.

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

        The input starts on top of the input stack
Z       Tuck a zero underneath the top value in the stack.  Both values end up on the main stack.
D       Drop the first element from array
F       For each remaining element (the leaves) run the rest of the program
  G^    Recursively call the entire program, then increment
  T     Get maximum of the two numbers now ow the stack

Запустите этот

рекурсивный
источник
0

Котлин, 45 байт

val Tree.h:Int get()=1+maxOf(l?.h?:0,r?.h?:0)

Предполагая, что следующий класс определен

class Tree(var v: Int, var l: Tree? = null, var r: Tree? = null)

Попробуйте онлайн

Асо Лео
источник
0

Юлия, 27 байт

f(t)=t≢()&&maximum(f,t.c)+1

Со следующей структурой, представляющей двоичное дерево:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

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

user3263164
источник