INF2220 l?sningsforslag uke 1 (27/8-31/8)
=========================================



OPPGAVE 2:
----------

a)   Big-O klassifisering:  O(n^2)

b)   Big-O klassifisering:  O(log2(n))	




OPPGAVE 4:
----------

Det er selvsagt flere m?ter ? l?se denne oppgaven p?,
men her kommer i alle fall et forslag. 




------------------------- Main.java -------------------------------


import java.util.LinkedList;


class Main{

	public static void main(String[] args){

		TreeNode root = new TreeNode("one");
		TreeNode t2 = new TreeNode("two");
		TreeNode t3 = new TreeNode("three");
		TreeNode t4 = new TreeNode("four");
		TreeNode t5 = new TreeNode("five");
		TreeNode t6 = new TreeNode("six");
		TreeNode t7 = new TreeNode("seven");
		TreeNode t8 = new TreeNode("eight");
		TreeNode t9 = new TreeNode("nine");
		TreeNode t10 = new TreeNode("ten");
		TreeNode t11 = new TreeNode("eleven");
		TreeNode t12 = new TreeNode("twelve");

		root.addChild(t2);
		root.addChild(t3);
		t2.addChild(t4);
		t2.addChild(t5);
		t2.addChild(t6);
		t4.addChild(t7);
		t5.addChild(t8);
		t5.addChild(t9);
		t5.addChild(t10);
		t5.addChild(t11);
		t5.addChild(t12);

		System.out.println("\nmax number of children : "+root.max()+"\n");

		root.prettyPrint();

		System.out.println("\nSearching for node 'seven'. found = "+root.findNode("seven"));
		System.out.println("\nSearching for node 'twenty'. found = "+root.findNode("twenty"));

	}



}




class TreeNode {

	TreeNode(String _id){
		this.id = _id;
		this.children = new LinkedList<TreeNode>();
	}

	String id;
	LinkedList<TreeNode> children;


	void addChild(TreeNode t){
		this.children.add(t);
	}

	int size(){
		return children.size();
	}

	int max(){

		int tmp = this.size();

		for(TreeNode child : children){
			int ny = child.max();
			if(ny > tmp){
				tmp = ny;
			}
		}
		return tmp;
	}



	public boolean findNode(String _id){
		boolean found = false;
		if( ! this.id.equals(_id )){
			for(TreeNode child : this.children){
				found = child.findNode(_id);
				if(found){
					break;
				}
			}
		}
		else{
			found = true;
		}
		return found;
	}

	public String toString(){
		return id;
	}



	/**
	*	fake default value with overloaded
	*	prettyPrint function, ie, we fake this
	*	construct:
	*
	*	  prettyPrint(spacer="")
	*
	*	since the root-node needs no spacing	
	*
	*/

	void prettyPrint(){
		prettyPrint("");
	}

	void prettyPrint(String spacer){

		System.out.println(spacer + this);

		for(TreeNode child : children){
				child.prettyPrint(spacer.replace('|','-').replace('-',' ') + "|--- ");
		}
	}

}