04 July 2011

Simple N Ad-hoc Tree Datastructure

Salam,

I needed to have some tree data structure ..

This tree have more than 2 childern with no particular order among them.

So I decided to write this simple implementation myself.
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;

public class XSGBTree<T>
{
    private Node root;
    
    public XSGBTree(T rootInfo)
    {
        root = new Node(rootInfo);
    }
    
    public Node getRoot()
    {
        return root;
    }
    
    public Node insert(T info, Node parent)
    {
        Node node = new Node(info);
        parent.getChildNodes().add(node);
        return node;
    }
    
    public void traverse(PrintStream out)
    {
        traverse(root, out);
    }
    
    public void traverse(Node node, PrintStream out)
    {
        out.println("Node: " + node.information);
        List<Node> childNodes = node.getChildNodes();
        System.out.println("Childern: "  + childNodes.size());

        for (int i=0; i< childNodes.size() ; i++)
        {
            out.println("child #:" + i + "\t" + childNodes.get(i).information);
            traverse(childNodes.get(i), out);    
        }
    }

    class Node
    {
        T information;
        Node parent;
        List<Node> childNodes = new ArrayList<XSGBTree<T>.Node>();

        public Node(T information)
        {
            this.information = information;
        }
        
        public List<Node> getChildNodes()
        {
            return childNodes;
        }
        
        boolean isRoot()
        {
            return this.parent == null;
        }

        boolean isLeaf()
        {
            return childNodes.size() == 0;
        }

        boolean isNode()
        {
            return !isLeaf();
        }
    }
}

Test class:

import xmlschemaparsing.XSGBTree.Node;


//http://en.wikipedia.org/wiki/File:Binary_search_tree.svg

public class XSGBTreeTest
{
    public static void main(String[] args)
    {
        XSGBTree<String> xsgbTree = new XSGBTree<String>("8");
        Node rootNode = xsgbTree.getRoot();
        Node node3 = xsgbTree.insert("3", rootNode);
        Node node8 = xsgbTree.insert("10", rootNode);
        
        Node node1 = xsgbTree.insert("1", node3);
        Node node6 = xsgbTree.insert("6", node3);
        Node node7 = xsgbTree.insert("7", node3);
        
        xsgbTree.traverse(System.out);
    }
}

No comments: