найти высоту дерева в sml

Question

Я хочу найти высоту дерева в sml. Дерево не является обычным, оно может иметь любое количество узлов на уровне. Кроме того, типы данных, которые оно содержит, также абстрактны. Может ли кто-нибудь помочь мне с этим.

Answer 1

Как уже говорили другие, тогда, пожалуйста, опубликуйте какое у вас есть определение дерева и какой код вы уже придумали.

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

datatype 'a tree = Leaf
                 | Node of ('a tree) * 'a * ('a tree)


val t1 = Node (Leaf, 1,  Leaf)
val t2 = Node (t1, 2, Leaf)

val t3 = Node (Leaf, 3, Leaf)

val t = Node (t2, 4, t3)

Ascii представление t

          4
        /   \
       /     \
      2       3
     / \     / \
    1   *   *   *
   / \
  *   *

Where * represents the leafs

Учитывая это представление двоичного дерева, вы можете создать функцию, которая вычисляет высоту в восходящем порядке.В основном вам нужно рассмотреть два случая:

1. Какова высота дерева, содержащего только лист?
2. Какова высота узла, у которого есть левое поддеревовысота l и правое поддерево высоты r?

Если мы посмотрим на t2 из приведенного выше примера

      2
     / \
    1   *
   / \
  *   *

Тогда, очевидно, правое поддерево имеет высоту x (зависит от того, как вы определяете высоту листьев)и левое поддерево имеет высоту 0. Высота t2 должна тогда быть 1 (0 + 1).

Учитывая t, тогда у него есть левое поддерево высоты 1 (как мытолько что обнаружил) и правое поддерево имеет высоту 0. Таким образом, t должно иметь высоту 2 (1 + 1)

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

Здесь

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