Leaf Trees - Height

0

It is usual to define trees where the information is only in leaf trees:

data LTree a = Tip a | Fork (LTree a) (LTree a)

Define the following function on this type:

ltHeight :: LTree a -> Int that calculates the height of a tree.

    
asked by anonymous 29.11.2017 / 20:05

1 answer

0

Using recursion, the solution is usually considered:

  • Tree without nodes (trivial case)
  • Tree with nodes (recursive case)

The size of a tree without nodes, ie, only the leaf, is 0. How to calculate the size of a multi-node tree? Simple, it is 1 plus the size of the subtree of greater height.

Knowing this, the implementation is simple:

ltHeight :: LTree a -> Int
ltHeight (Tip l)    = 0                                 -- Caso trivial
ltHeight (Fork e d) = 1 + max (ltHeight e) (ltHeight d) -- 1 + altura da maior sub-arvore

Here is the link to an example:

    
29.11.2017 / 21:43