// h5_t1.java SJ

import fi.joensuu.cs.tra.*;
import java.util.LinkedList;

public class h5_t1 {

	public static void main(String[] args) {

		Tree<Integer> puu = exampleTree();

		System.out.println("Esijärjestyksessä listassa:");
		LinkedList<Integer> l = preorderList(puu);

		System.out.println(l);
		
	} // main()


	// rakentaa pienen esijärjestetyn yleisen puun
	public static Tree<Integer> exampleTree() {
		Tree<Integer> puu = new Tree<Integer>();

		TreeNode<Integer> n, m, l = null, k;

		/* rakennetaan tällainen puu:

			1
		  //\\
		 /|  |\
		/ |  | \
	   2  6 10  14_____________
	  / \ |  |  |  \  \  \  \  \
	  3 5 8 11  15 16 17 18 19 20
			 |
			12
		*/

		// juuri
		n = new TreeNode<Integer>(1);
		puu.setRoot(n);

		// juuren vasemmanpuoleisin lapsi
		m  = new TreeNode<Integer>(2);
		n.setLeftChild(m);

		// juuren muut lapset
		for (int i = 6 ; i <= 14 ; i+=4) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		// 2:n lapset
		m = puu.getRoot().getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(3));
		m.getLeftChild().setRightSibling(new TreeNode<Integer>(5));

		// 6:n lapsi
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(8));

		// 10:n lapsi
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(11));
		// 10:n lapsenlapsi
		m = m.getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(12));

		// 14:n lapset
		m = new TreeNode<Integer>(15);
		l.setLeftChild(m);
		for (int i = 16 ; i <= 20 ; i++) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		System.out.println("        1");
		System.out.println("      //\\\\");
		System.out.println("     /|  |\\");
		System.out.println("    / |  | \\");
		System.out.println("   2  6 10  14_____________");
		System.out.println("  / \\ |  |  |  \\  \\  \\  \\  \\");
		System.out.println("  3 5 8 11  15 16 17 18 19 20");
		System.out.println("         |");
		System.out.println("        12");
		System.out.println();

		return puu;

	} // exampleTree()


	// Tulostus esijärjestyksessä rekursiivisesti
	public static LinkedList preorderList(Tree T) {
        LinkedList L = new LinkedList();
        preorderListBranch(T.getRoot(), L);
		return L;
	} // preorderList()


	public static void preorderListBranch(TreeNode n, LinkedList L) {
		L.add(n.getElement());
		TreeNode child = n.getLeftChild();
		while (child != null) {
			preorderListBranch(child, L);
			child = child.getRightSibling();
		}
	} // preorderListBranch()



} // class h5_t1

============================================================================

// h5_t2_3 SJ

import fi.joensuu.cs.tra.*;
import java.util.LinkedList;

public class h5_t2_3 {

	public static void main(String[] args) {

		Tree<Integer> puu = exampleTree();

		System.out.println("Esijärjestyksessä:");
		preorderPrint(puu);

		System.out.println("Tasoittain:");
		printByLevel(puu);

		for (int i = 1; i < 21; i++) {
			System.out.println("Solmu " + i + " : " +
							   preorderSearch(puu, new Integer(i)) +
							   " kork: " + korkeus(preorderSearch(puu, new Integer(i))));
		}

		System.out.println("Matalin : " + matalin(puu));

		puu = kuusipuu(3);

		System.out.println("Kuusipuu 3");
		System.out.println("Esijärjestyksessä:");
		preorderPrint(puu);

		System.out.println("Tasoittain:");
		printByLevel(puu);


		



		

		
	} // main()


	// rakentaa pienen esijärjestetyn yleisen puun
	public static Tree<Integer> exampleTree() {
		Tree<Integer> puu = new Tree<Integer>();

		TreeNode<Integer> n, m, l = null, k;

		/* rakennetaan tällainen puu:

			1
		  //\\
		 /|  |\
		/ |  | \
	   2  6 10  14_____________
	  / \ |  |  |  \  \  \  \  \
	  3 5 8 11  15 16 17 18 19 20
			 |
			12
		*/

		// juuri
		n = new TreeNode<Integer>(1);
		puu.setRoot(n);

		// juuren vasemmanpuoleisin lapsi
		m  = new TreeNode<Integer>(2);
		n.setLeftChild(m);

		// juuren muut lapset
		for (int i = 6 ; i <= 14 ; i+=4) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		// 2:n lapset
		m = puu.getRoot().getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(3));
		m.getLeftChild().setRightSibling(new TreeNode<Integer>(5));

		// 6:n lapsi
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(8));

		// 10:n lapsi
		m = m.getRightSibling();
		m.setLeftChild(new TreeNode<Integer>(11));
		// 10:n lapsenlapsi
		m = m.getLeftChild();
		m.setLeftChild(new TreeNode<Integer>(12));

		// 14:n lapset
		m = new TreeNode<Integer>(15);
		l.setLeftChild(m);
		for (int i = 16 ; i <= 20 ; i++) {
			l = new TreeNode<Integer>(i);
			m.setRightSibling(l);
			m = l;
		}

		System.out.println("        1");
		System.out.println("      //\\\\");
		System.out.println("     /|  |\\");
		System.out.println("    / |  | \\");
		System.out.println("   2  6 10  14_____________");
		System.out.println("  / \\ |  |  |  \\  \\  \\  \\  \\");
		System.out.println("  3 5 8 11  15 16 17 18 19 20");
		System.out.println("         |");
		System.out.println("        12");
		System.out.println();

		return puu;

	} // exampleTree()


	// Tulostus esijärjestyksessä rekursiivisesti
	public static void preorderPrint(Tree T) {
		if (T.getRoot() != null)
			preorderPrintBranch(T.getRoot());
		System.out.println();
	} // preorderPrint()


	public static void preorderPrintBranch(TreeNode n) {
		System.out.print(n.getElement() + " ");
		TreeNode child = n.getLeftChild();
		while (child != null) {
			preorderPrintBranch(child);
			child = child.getRightSibling();
		}
	} // preorderPrintBranch()


	// Tulostus tasoittain
	public static void printByLevel(Tree T) {
		LinkedQueue<TreeNode> Q = new LinkedQueue<TreeNode>();
		if (T.getRoot() != null)
			Q.offer(T.getRoot());

		while (! Q.isEmpty()) {
			TreeNode n = Q.poll();
			System.out.print(n.getElement() + " ");
			n = n.getLeftChild();
			while (n != null) {
				Q.offer(n);
				n = n.getRightSibling();
			}
		}
		System.out.println();
	} // printByLevel()


	public static TreeNode preorderSearch(Tree T, Comparable x) {
		TreeNode n = T.getRoot();

		while (n != null) {

			// tarkastetaan josko sattui
			if (x.compareTo(n.getElement()) == 0)
				return n;

			// jollei oikeaa veljeä ole, tai se on haettavaa suurempi, mennään vasemmalle alas
			if ((n.getRightSibling() == null) ||
				(x.compareTo(n.getRightSibling().getElement()) < 0))
				n = n.getLeftChild();
			else // muuten mennään oikealle
				n = n.getRightSibling();

		} // while

		return null;

	} // preorderSearch()


	public static Tree<Integer> kuusipuu(int k) {

		Tree<Integer> T = new Tree<Integer>();
		TreeNode<Integer> n = new TreeNode<Integer>(0);

		T.setRoot(n);
		
		TreeNode<Integer> runko = n;
		while (k > 0) {

			// vasen lehvä
			n = new TreeNode<Integer>(k*10);
			runko.setLeftChild(n);

			// runko
			runko = new TreeNode<Integer>(k*10+1);
			n.setRightSibling(runko);

			// oikea lehvä
			runko.setRightSibling(new TreeNode<Integer>(k*10+2));

			k--;
		} // while

		return T;

	} // kuusipuu()


	public static int korkeus(TreeNode n) {

		// varotoimenpide
		if (n == null)
			return -1;

		// haetaan korkein lapsi
		int l, max = -1;
		TreeNode child = n.getLeftChild();
		while (child != null) {
			l = korkeus(child);
			if (l > max)
				max = l;
			child = child.getRightSibling();
		}

		// oma korkeus on yhtä enemmän
		return max + 1;

	} // korkeus()


	public static TreeNode matalin(Tree T) {

		if (T.getRoot() == null)
			return null;

		LinkedQueue<TreeNode> Q = new LinkedQueue<TreeNode>();
		Q.offer(T.getRoot());

		while (! Q.isEmpty()) {
			TreeNode n = Q.poll();

			// tasoittain ensimmäinen lehtisolmu
			if (n.getLeftChild() == null)
				return n;

			n = n.getLeftChild();
			while (n != null) {
				Q.offer(n);
				n = n.getRightSibling();
			}
		} // while

		return null; // tänne ei koskaan tulla, mutta kääntäjä vaatii tämän...

	} // matalin


} // class h5_t2_3

==========================================================================

// h5_t4_6.java SJ

import fi.joensuu.cs.tra.*;
import java.util.Random;

public class h5_t4_6 {

	public static void main(String[] args) {

		BTree<Integer> puu = new BTree<Integer>();

		int N = 10;
		if (args.length > 0)
			N = Integer.valueOf(args[0]);

		System.out.println("Puuhun:");
		Random r = new Random(42);
		Integer x;
		for (int i = 0; i < N; i++) {
			x = r.nextInt(N*2);
			System.out.print(x + " ");
			inorderInsert(puu, x);
		}
		System.out.println();

		System.out.println("Sisajarjestyksessa:");
		inorderPrint(puu);

		for (int i = 0; i < 16; i++) {
			System.out.println("Onko " + i + " : " +
							   inorderMember(puu, new Integer(i)));
		}

		puu = exampleBTree();
		
		System.out.println("Sisajarjestyksessa:");
		inorderPrint(puu);

		BTree<Integer> puu2 = exampleBTree();

		System.out.println("Samat : " + vertaaRakenne(puu, puu2));

		System.out.println("Matalin lehti : " + matalinLehtiSolmu(puu2).getElement());

		System.out.println("Poistetaan puusta1: 3");
		inorderRemoveNode(puu, inorderFindNode(puu, 3));
		System.out.println("Samat : " + vertaaRakenne(puu, puu2));
                inorderPrint(puu);

                System.out.println("Poistetaan puusta2 : 3");
                inorderRemoveNode(puu2, inorderFindNode(puu2, 3));
                System.out.println("Samat : " + vertaaRakenne(puu, puu2));
                inorderPrint(puu);


                /* System.out.println("Lisätään: 2");
                inorderInsert(puu, 2);
                inorderPrint(puu);
                System.out.println("Samat : " + vertaaRakenne(puu, puu2));
                
                System.out.println(); */
		
	} // main()

	/* Luo pienen sisajarjestyn esimerkkipuun
	                 
	       10        
	    __/  \__     
	   5        15   
	  / \      /  \  
	 3   8   12    18
	  \      /\      
	   4    11 13    
	                 
	*/
	public static BTree<Integer> exampleBTree() {

		BTree<Integer> T = new BTree<Integer>();

		// juuri
		T.setRoot(new BTreeNode<Integer>(10));

		BTreeNode<Integer> n = T.getRoot();

		// juuren lapset
		n.setLeftChild(new BTreeNode<Integer>(5));
		n.setRightChild(new BTreeNode<Integer>(15));

		// vasen haara
		BTreeNode<Integer> l = n.getLeftChild();

		l.setLeftChild(new BTreeNode<Integer>(3));
		l.setRightChild(new BTreeNode<Integer>(8));

		l.getLeftChild().setRightChild(new BTreeNode<Integer>(4));

		// oikea haara
		l = n.getRightChild();

		l.setLeftChild(new BTreeNode<Integer>(12));
		l.setRightChild(new BTreeNode<Integer>(18));

		l.getLeftChild().setLeftChild(new BTreeNode<Integer>(11));
		l.getLeftChild().setRightChild(new BTreeNode<Integer>(13));


		System.out.println("                 ");
		System.out.println("       10        ");
		System.out.println("    __/  \\__     ");
		System.out.println("   5        15   ");
		System.out.println("  / \\      /  \\  ");
		System.out.println(" 3   8   12    18");
		System.out.println("  \\      /\\      ");
		System.out.println("   4    11 13    ");
		System.out.println("                 ");

		return T;

	} // exampleBTree()


	public static boolean inorderInsert(BTree T, Comparable x) {
		BTreeNode n = T.getRoot();
		if (n == null) {
			T.setRoot(new BTreeNode(x));
			return true;
		}

		while (true) {

			if (x.compareTo(n.getElement()) == 0)
				// x jo puussa, eli lisata
				return false;
			
			else if (x.compareTo(n.getElement()) < 0) {
				// x edeltaa n:n alkiota
				if (n.getLeftChild() == null) {
					// lisayskohta loydetty
					n.setLeftChild(new BTreeNode(x));
					return true;
				} else
					n = n.getLeftChild();
			} else {
				// x suurempi kuin n
				if (n.getRightChild() == null) {
					// lisayskohta loydetty
					n.setRightChild(new BTreeNode(x));
					return true;
				} else
					n = n.getRightChild();
			}
		} // while

	} // inorderInsert()


	// etsii annettua elementtia puusta, palauttaa totuusarvon
	public static boolean inorderMember(BTree T, Comparable x) {
		BTreeNode n = T.getRoot();

		while (n != null) {
			if (x.compareTo(n.getElement()) == 0)
				return true;
			else if (x.compareTo(n.getElement()) < 0)
				n = n.getLeftChild();
			else
				n = n.getRightChild();
		} // while
		return false;

	} // inorderMember()


	// etsii annetun elementin sisaltavan solmun
	public static BTreeNode inorderFindNode(BTree T, Comparable x) {
		BTreeNode n = T.getRoot();

		while (n != null) {
			if (x.compareTo(n.getElement()) == 0)
				return n;
			else if (x.compareTo(n.getElement()) < 0)
				n = n.getLeftChild();
			else
				n = n.getRightChild();
		} // while
		return null;

	} // inorderMember()

    // matalin lehtisolmu tasoittaisella läpikäynnillä
    public static BTreeNode matalinLehtiSolmu(BTree T) {

        if (T.getRoot() == null)
            return null;
        // juuri jonoon
        LinkedQueue<BTreeNode> Q = new LinkedQueue<BTreeNode>();
        Q.offer(T.getRoot());

        while (true) {
            BTreeNode n = Q.poll();
            BTreeNode l = n.getLeftChild();
            BTreeNode r = n.getRightChild();

            // jollei lapsia, matalin on löytynyt
            if (l == null && r == null)
                return n;

            // muuten lapsen jonoon
            if (l != null)
                Q.offer(l);
            if (r != null)
                Q.offer(r);
        }

    } // matalinLehtiSolmu()



	public static BTreeNode inorderNext(BTreeNode n) {

		// jos solmulla on oikea lapsi, haetaan sen
		// vasemmanpuoleinen jalkelainen

		if (n.getRightChild() != null) {
			BTreeNode m = n.getRightChild();
			while (m.getLeftChild() != null)
				m = m.getLeftChild();
			return m;
		}

		// muutoin haetaan ensimmainen esivanhempi jonka
		// vasemmassa alipuussa solmu n on

		else {
			BTreeNode m = n;
			BTreeNode par = n.getParent();
			while (par != null) {
				if (par.getLeftChild() == m)
					return par;
				else {
					m = par;
					par = par.getParent();
				}
			}

		}

		// jollei loytynyt
		return null;

	} // inorderNext()


	// poistaa annetun solmun siten, etta puu sailyy sisajarjestyksessa
	public static void inorderRemoveNode(BTree T, BTreeNode n) {


		// sukulaiset apumuuttujiin
		BTreeNode lc = n.getLeftChild();
		BTreeNode rc = n.getRightChild();

		BTreeNode par = n.getParent();

		// muistetaan onko n vanhempansa oikea vai vasen lapsi
		boolean vasen = false;
		if (par != null) {
			if (par.getLeftChild() == n)
				vasen = true;
			else
				vasen = false;
		}

		// 0-1 -lapsiset tapaukset erikseen

		// jos juuri, ei vasenta lasta: oikea lapsi tilalle
		if (n == T.getRoot() && lc == null)
			T.setRoot(rc);

		// jos juuri, ei oikeaa lasta: vasen lapsi tilalle
		else if (n == T.getRoot() && rc == null)
			T.setRoot(lc);

		// jos ei juuri, ei vasenta lasta: oikea lapsi tilalle
		else if (lc == null) {
			if (vasen)
				par.setLeftChild(rc);
			else
				par.setRightChild(rc);
		}

		// jos juuri, ei oikeaa lasta: vasen lapsi tilalle
		else if (rc == null) {
			if (vasen)
				par.setLeftChild(lc);
			else
				par.setRightChild(lc);
		}


		// molemmat lapset olemassa
		else {

			BTreeNode korv = inorderNext(n);
			Object korvAlkio = korv.getElement();

			// poistetaan korvaava rekursiivisesti
			inorderRemoveNode(T, korv);

			// uusi alkio vanhan tilalle
			n.setElement(korvAlkio);

		}

	} // inorderRemoveNode


	// Tulostus sisajarjestyksessa rekursiivisesti
	public static void inorderPrint(BTree T) {
		inorderPrintBranch(T.getRoot());
		System.out.println();
	} // inorderPrint()


	public static void inorderPrintBranch(BTreeNode n) {
		if (n == null)
			return;

		inorderPrintBranch(n.getLeftChild());
		System.out.print(n.getElement() + " ");
		inorderPrintBranch(n.getRightChild());

	} // inorderPrintBranch()


	// Kahden binääripuun vertailu
	public static boolean vertaaRakenne(BTree T1, BTree T2) {
		return vertaaRakenneOksa(T1.getRoot(), T2.getRoot());
	} // vertaaRakenne()


	public static boolean vertaaRakenneOksa(BTreeNode n1, BTreeNode n2) {

		// molemmat null on ok
		if (n1 == null && n2 == null)
			return true;

		// vain jompikumpi null -> eri puut
		if (n1 == null || n2 == null)
			return false;

		// vasempien ja oikeiden oltava samat
		return vertaaRakenneOksa(n1.getLeftChild(), n2.getLeftChild()) &&
			vertaaRakenneOksa(n1.getRightChild(), n2.getRightChild());

	} // vertaaRakenneOksa()

	
} // class h5_t4_6