Java tree implementation

Question

I was given the following tree:

And then we were told to use the last-child / previous-sibling method to change the implementation of these three. This led to the following:

Now I am working on a Java implementation to perform various functions on this tree. We have a Tree interface and a TreeNode interface. Both of them have many functions that we must fill.

Nodes are created as follows:

MyTreeNode a = new MyTreeNode ("a"); 

The tree is created (using root) as follows:

 MyTree tree = new MyTree (a); 

And finally, the nodes are given sibling children as such:

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

I already wrote 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; } 

Now I completely lost information on how to write methods for height, depth, size of the subtree node, getPreOrder, getPostOrder and tree size.

Since the tree is now in this other view, I'm not sure how to write recursive methods to check the height or depth of a node. Usually, as I understand it, you would recursively check the left / right subtrees .. but now they are gone (as far as I can see). The only way I could do this is to loop through each node with many if and while statements, but this is not the best way to do this.

How can I write these methods recursively using this tree implementation?

Also, I'm not sure how to get detailed information about the whole tree, since the nodes are not stored together. They are implemented as I showed above, so I'm not sure how to collect data about all nodes collectively.

How can I create methods like tree size, isEmpty or makeEmpty, for all nodes as a whole tree?

Sorry for the overly detailed explanation.

Answer 1

Suppose you have a node structure similar to 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 is what I think about how I will build a new tree. When you add new nodes to your tree, you will still maintain your tree structure. Depending on how you add your nodes to the tree, you still continue to add either to the left or to the right of your parent.

One possible way to visualize a new tree would be something like this:

  A / E / \ DJ / \ / \ CHIK / B / G / F 

Note. I suggested that if this is an only child, it will be added to the left of your parent. But this ideally will depend on your requirement

If you can visualize this tree in this way, your recursive functions for obtaining heights, pre-orders, postoperations are still the same.

A few tips:

• Adding a brother would be like adding a node to the left or right of the parent node, i.e. if the current node is to the left of it, you should add a new node to the right.

• Adding a child will remain the same. Depending on your logic, you will add a new node as the left child or right child of your current node.