// TRAI_23_t14_15.java.java SJ
/**
* 14. Kirjoita algoritmi joka laskee annetun binääripuun korkeuden, ts. pisimmän polun juuresta
* lehtisolmuun. Aikavaativuus? Vihje: rekursio.
*
* 15. Kirjoita algoritmi joka lisää sisäjärjestyksessä olevaan binääripuuhun uuden solmun siten,
* että puu säilyy sisäjärjestyksessä. Jos sama alkio (.equals()) oli jo puussa, niin alkiota ei
* lisätä puuhun. Parametreina puu ja alkio. Algoritmi luo uuden solmun jos lisäys tehdään.
* Algoritmi palauttaa totuusarvon lisättiinkö alkio vai ei. Algoritmin toiminta käydään
* läpi luennolla. Aikavaativuus?
*/
// Tarvitset projektiin (tai komentoriville) TRA-kirjaston Moodlesta.
import fi.uef.cs.tra.BTree;
import fi.uef.cs.tra.BTreeNode;
import java.util.Random;
public class TRAI_23_t14_15_pohja {
public static void main(String[] args) {
BTree puu = new BTree();
int N = 12;
if (args.length > 0)
N = Integer.parseInt(args[0]);
// testataan ensin vakiopuulla
puu = exampleBTree();
System.out.println("Sisäjärjestyksessä:");
inorderPrint(puu);
System.out.println("Korkeus = " + korkeus(puu));
System.out.println();
// tehdään vielä uusi generoitu ja testataan samalla
// tehtävää 15
puu = new BTree<>();
System.out.println("\nPuuhun:");
Random r = new Random(42);
Integer x = null;
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("Sisäjärjestyksessä:");
inorderPrint(puu);
System.out.println("Korkeus = " + korkeus(puu));
// testataan vielä hakemista
for (int i = 0; i < N * 2; i++) {
System.out.println("Onko " + i + " : " +
inorderMember(puu, i));
}
} // main()
/**
* 14. Puun korkeus. Käynnistysmetodi
* @param t tarkasteltava binääripuu.
* @return puun korkeus tai -1 jos puu on tyhjä
**/
public static int korkeus(BTree t) {
// TODO
return 0;
}
/**
* Solmun korkeus.
* @param n tarkasteltava solmu
* @return solmun korkeus, tai -1 jos n==null
*/
public static int korkeus(BTreeNode n) {
// TODO
return 0;
}
/**
* 15. Lisäys sisäjärjestettyyn binääripuuhun.
* @param T binääripuu
* @param lisattavaAlkio lisättävä alkio
* @return tehtiinkö lisäys vai ei
*/
public static > boolean inorderInsert(BTree T, E lisattavaAlkio) {
// jos puu on tyhjä, lisätään juureksi
BTreeNode n = T.getRoot();
if (n == null) {
T.setRoot(new BTreeNode(lisattavaAlkio));
return true;
}
// muuten etsitään paikka ja jos törmätään tyhjään solmuun, lisätään sen tilalle
// TODO
return false;
} // inorderInsert()
// -------------------------------
// esimerkkejä
public static BTree exampleBTree() {
BTree T = new BTree();
// juuri
T.setRoot(new BTreeNode(9));
BTreeNode n = T.getRoot();
// juuren lapset
n.setLeftChild(new BTreeNode(5));
n.setRightChild(new BTreeNode(15));
// vasen haara
BTreeNode l = n.getLeftChild();
l.setLeftChild(new BTreeNode(3));
l.setRightChild(new BTreeNode(8));
l.getLeftChild().setRightChild(new BTreeNode(4));
// oikea haara
l = n.getRightChild();
l.setLeftChild(new BTreeNode(12));
l.setRightChild(new BTreeNode(18));
l.getLeftChild().setLeftChild(new BTreeNode(11));
l.getLeftChild().setRightChild(new BTreeNode(13));
System.out.println(" ");
System.out.println(" 9 ");
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()
/**
* Onko alkio sisäjärjestetyssä binääripuussa vai ei
* @param T sisäjärjestetty binääripuu
* @param x etsittävä alkio
* @param alkiotyyppi
* @return true jos alkio x on puussa, muuten false
*/
public static >
boolean inorderMember(BTree T, E 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()
/**
* Tulostus sisäjärjestyksessä rekursiivisesti.
* @param T tulostettava puu
*/
public static void inorderPrint(BTree T) {
inorderPrintBranch(T.getRoot());
System.out.println();
} // inorderPrint()
/**
* Tulostus sisäjärjestyksessä rekursiivisesti.
* @param n tulostettavan alipuun juuri
*/
public static void inorderPrintBranch(BTreeNode n) {
if (n == null)
return;
inorderPrintBranch(n.getLeftChild());
System.out.print(n.getElement() + " ");
inorderPrintBranch(n.getRightChild());
} // inorderPrintBranch()
} // class TRAI_23_t14_15.java