tree structures

Discussion in 'Java' started by shawn, Mar 7, 2006.

  1. shawn

    shawn Guest

    Does anyone know how to calculate the height of a tree structure? The
    height should be for the maximum size branch. My tree is mad up with
    nodes that have a getLeft and getRight method. getLeft and getRight
    return the reference to the node in that position, or null if there
    isnt one there.
     
    shawn, Mar 7, 2006
    #1
    1. Advertising

  2. shawn

    Jacob Guest

    shawn wrote:

    > Does anyone know how to calculate the height of a tree structure? The
    > height should be for the maximum size branch. My tree is mad up with
    > nodes that have a getLeft and getRight method. getLeft and getRight
    > return the reference to the node in that position, or null if there
    > isnt one there.


    Something like:

    int getDepth(Node node, int depth)
    {
    int leftDepth = depth;
    int rightDepth = depth;

    if (node.getLeft())
    leftDepth = getDepth(node.getLeft(), depth + 1);
    if (node.getRight())
    rightDepth = getDepth(node.getRight(), depth + 1);

    return max(leftDepth, rightDepth);
    }


    Call by getDepth(root, 1)

    NOT tested :)
     
    Jacob, Mar 7, 2006
    #2
    1. Advertising

  3. "shawn" <> wrote in message
    news:...
    > Does anyone know how to calculate the height of a tree structure? The
    > height should be for the maximum size branch. My tree is mad up with
    > nodes that have a getLeft and getRight method. getLeft and getRight
    > return the reference to the node in that position, or null if there
    > isnt one there.


    int getHeight (Node node) {
    if (node == null) return 0;

    return 1 + Math.max (getHeight(node.getLeft()),
    getHeight(node.getRight()));
    }

    getHeight (rootNode)

    or implicitly as a method of Node

    int getHeight () {
    int leftHeight = getLeft() != null ? getLeft.getHeight() : 0;
    int rightHeight = getRight () != null ? getRight.getHeight () : 0;

    return 1 + Math.max (leftHeight, rightHeight);
    }

    rootNode.getHeight ()

    Cheers,
    Matt Humphrey http://www.iviz.com/
     
    Matt Humphrey, Mar 7, 2006
    #3
  4. shawn

    shawn Guest

    thanks guys
     
    shawn, Mar 7, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    533
  2. Replies:
    3
    Views:
    462
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,242
  4. tweak
    Replies:
    14
    Views:
    2,820
    Eric Sosman
    Jun 11, 2004
  5. Alfonso Morra
    Replies:
    11
    Views:
    754
    Emmanuel Delahaye
    Sep 24, 2005
Loading...

Share This Page