2 Replies - 2747 Views - Last Post: 11 December 2010 - 01:29 PM Rate Topic: -----

#1 FNHA  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 14-October 10

Converting binary tree to general tree

Posted 11 December 2010 - 11:54 AM

Hi, I have to write a program that reads an encoded binary tree from a text file and builds it in memory. I have managed to get the binary tree working fine, but I'm stuck at building the general tree from the binary tree. When I try to add the children to the node, I get an ArrayStoreException, and I can't find where exactly the mistake in data type occurred.

This is my code for building the general tree. rootSC is the root node from the binary tree.
public void buildGTree() {
        rootGT = buildGTree(rootSC);
    }
    
    private GTNode<T> buildGTree(SiblingNode<T> item) {
        GTNode<T> thisNode = new GTNode(item.data);
        if (item.leftChild != null) {
            SiblingNode<T> leftMostChild = item.leftChild;
            SiblingNode<T> sibling = leftMostChild.rightSibling;
            System.out.println("Adding child of " + thisNode.data);
            thisNode.children.add(buildGTree(leftMostChild));
            System.out.println(leftMostChild.data + " is a child of " + thisNode.data);
            while (sibling != null) {
                thisNode.children.add(buildGTree(sibling));
                System.out.println(sibling.data + " is a child of " + thisNode.data);
                sibling = sibling.rightSibling;
            }
        }
        return thisNode;
    }


These are the inner classes for the binary tree node (SiblingNode) and general tree node (GTNode).

private class GTNode<T> {
        private T data;
        private ArrayList<GTNode<T>> children;
        
        public GTNode(T item) {
            data = item;
            children = new ArrayList();
        }
    }
    
    private class SiblingNode<T> {
        private T data;
        private SiblingNode<T> leftChild;
        private SiblingNode<T> rightSibling;
        
        public SiblingNode(T item) {
            data = item;
            leftChild = null;
            rightSibling = null;
        }
    }


Is it an error in the build method that somehow causes the data type to be different when I add it into the array?

Is This A Good Question/Topic? 0
  • +

Replies To: Converting binary tree to general tree

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,585
  • Joined: 27-December 08

Re: Converting binary tree to general tree

Posted 11 December 2010 - 12:56 PM

What exactly are the specifications for the general Tree? Since a Binary Tree is a special case of a General Tree, I'm not exactly sure what you're trying to accomplish.
Was This Post Helpful? 0
  • +
  • -

#3 FNHA  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 14-October 10

Re: Converting binary tree to general tree

Posted 11 December 2010 - 01:29 PM

Specifically, the first Binary Tree represents a Leftmost-child Right-sibling tree, where a new level always starts with a leftmost child relation, then others on the same level and originating from the same parent being connected through right-sibling relationships. The general tree I'm supposed to convert them to is the type which can take any number of children instead of just two, basically taking the left child of the node and all its right siblings and making them the children of that node.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1