Tree Implementation in Java

Question

I was given the following tree:

Original tree

And then we were told to use last-child/previous-sibling method to change the implementation of the three. That resulted in the following:

Tree after last-child/previous-sibling method

I am now working on Java implementation to perform different functions on this tree. We have a Tree interface, and a TreeNode interface. They both have many functions that we are to fill out.

Nodes are created like this:

MyTreeNode a = new MyTreeNode ("a");

The tree is created (with a root) in this way:

MyTree     tree = new MyTree (a);

And lastly, nodes are given siblings children as such:

e.setChild(j);
e.setSibling(d);

I already wrote the methods for setChild, setSibling, getNextSibling, getFirstChild, and getChildren. For example, this is the code for getChildren:

public List getChildren ()
{
    List <MyTreeNode> children = new ArrayList <MyTreeNode> ();

    MyTreeNode x = this.child;

    children.add(x);

    while (x != null && x.sibling != null) {
        x = x.sibling;
        children.add(x);
    }

    return children;
}

I am now completely lost on how to write the methods for height, depth, size of a node's subtree, getPreOrder, getPostOrder, and tree size.

Since the tree is now in this different representation, I am not sure how to write recursive methods to check the height or depth of a node. Normally, as I understand, you would recursively check left/right subtrees.. but now there aren't any (as far as I can see). The only way I can think to do it would be looping through each and every node with many if statements and while loops.. but that can't be the best way to do it.

How can I write these methods recursively with this implementation of a tree?

Also, I am not sure how to get details about the whole tree since nodes are not stored together in any way. They are implemented in the way I showed above, so I'm not sure how to gather data about all the nodes collectively.

How can I create methods such as tree size, isEmpty, or makeEmpty, on all the nodes as a whole tree?

Sorry for the overly verbose explanation.

Sujay · Accepted Answer · 2012-09-18 00:59:49Z

2

Assuming that you have a node structure like this for your tree:

public class Node{
   String nodeName;

   Node left;
   Node right;

   public Node(String nodeName, Node left, Node right){
     this.nodeName = nodeName;
     this.left     = left;
     this.right= right;
   }
}

Here's what I think of how I would construct your new tree: When you're adding new nodes to your tree, you would still be maintaining your tree structure. Depending on how you add your nodes to the tree, you would still continue to add either to the left or right of your parent.

One possible way of visualizing the new tree would be something like this:

                A
               /
              E
            /   \
           D     J
         /   \   / \
        C    H  I   K
       /
      B
     /
    G
   /    
  F

Note: I've assumed over here that if it's a single child, it would be added to the left of your parent. But this would ideally depend on your requirement

If you can visualize this tree in this way, your recursive functions for getting the height, preorder, postorder traversal still remains the same.

A couple of more hints:

Adding a sibling would be like adding a node to either the left or right of the node's parent, i.e. if the current node is in the left of it's parent, you would add the new node in the right.
Adding a child would remain the same. Depending on your logic, you would add the new node as the left child or the right child of your current node.

answered Sep 18, 2012 at 0:59

Sujay

6,7812 gold badges32 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Jakemmarsh Over a year ago

Thank you for the response. However, I'm failing to see how to apply this to my specific tree structure... B, C, D, and E are all siblings, and all children of A... In your diagram, they are not siblings. Same problem with F & G, and I & K. Thus using this method would mess with the original structure of my tree. That is, unless I'm missing something.

Sujay Over a year ago

@Jakemmarsh: How do you define/differentiate between sibling and child?

Jakemmarsh Over a year ago

@Sujay - siblings are nodes that have the same parent node.. children are the nodes that come from a parent node?

FThompson Over a year ago

@Sujay In your diagram, D and J are siblings because they have the same parent. They are also both children of E. Siblings have the same parent; children have a parent.

Sujay Over a year ago

@Jakemmarsh: Going by that same definition of sibling, in your second image, B's parent is C, C's is D and D's parent is E, then how come C,D and E are siblings?

|

Collectives™ on Stack Overflow

Tree Implementation in Java

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related