finding height of a tree in sml

i want to find the height o开发者_运维知识库f a tree in sml.The tree is not a regular one it could have any number of nodes at a level.Futher the datatypes that it holds is also abstract.could someone help me out with it.

---

As other have said, then please post what ever definition of a tree you have, and what code you have come up with so far.

I assume that you have already defined your own tree structure or you have had it defined in the assignment, anyways this ought not to be your problem so here is simple binary tree structure using a Node and an empty Leaf as constructors.

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 representation of t

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

Where * represents the leafs

Given this representation of a binary tree, you could create a function that calculates the height in a bottom up maner. You mainly have to consider two cases:

1. What are the height of a tree only containing a leaf?
2. What are the height of a Node that has a left sub-tree of height l and a right sub-tree of height r?

If we look at t2 from the above example

      2
     / \
    1   *
   / \
  *   *

Then obviously the right sub-tree has height x (depends on how you define the height of leafs) and the left sub-tree has height 0. The Height of t2 must then be 1 (0+1).

Considering t then it has a left sub-tree of height 1 (as we have just found out) and the right sub-tree has height 0. Thus t must have height 2 (1+1)

I have seen many quick implementation of a height function that counts the root node, but this is not correct.

Here

height is defined as the number of links from the root to the deepest leaf