CODEWITHSUNDEEP
javatree
Jakemmarsh
Jakemmarsh

Reputation: 4671

Tree Implementation in Java

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.

Upvotes: 4

Views: 8691

Answers (1)

Sujay
Sujay

Reputation: 6783

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.

Upvotes: 2

Related Questions