Løsningsforslag 10
Fra Hiofwiki
Innhold |
[rediger]
Gruppe 118
[rediger]
Oppgave 10.1
A
/ \
B C
/ \ \
/ \ \
/ \ \
D E F
/ \ / \ \
G H I J K
/ \
L M
a) Hvilken node er rotnoden? A er rotnoden
b) Hvilke noder er blader i treet? G, H, L, M, J, K er bladene til treet
c) Hva er dybden til treet? Dybden er 5 (inkludert rotnoden)
d) Angi rekkefølgen som nodene oppsøkes i ved hhv. preorder, inorder, postorder og bredde-først traversering.
Preorder: A, B, D, G, H, E, I, L, M, J, C, F, K
Inorder: G, D, H, B, L, I, M, E, J, A, C, F, K
Postorder: G, H, D, L, M, I, J, E, B, K, F, C, A
Level-order: A, B, C, D, E, F, H, I, J, K, L, M
[rediger]
Oppgave 10.2
Angi, for hver node:
a) Foreldernoden
b) Barn
c) Søsken
d) Dybde (antall noder til dypeste bladnode, inkludert noden selv)
e) Størrelse (antall noder i subtreet med rot i denne nod
(lånt svaroppsett av Gruppe 4(Emil Krey), siden det var oversiktlig)
A B C D E F G H I J K L M a) A A B B C D D E E F I I b) B,C D,E F G,H I,J K L,M c) C B E D H G J I M L d) 5 4 3 2 3 2 1 1 2 1 1 1 1 e) 13 9 3 3 5 2 1 1 3 1 1 1 1
[rediger]
Oppgave 10.3
Hva skrives ut når følgende rekursive metode
public void mysteryPrint(BinaryNode t)
{
if (t != null)
{
System.out.println(t.element);
mysteryPrint(t.left);
System.out.println(t.element);
mysteryPrint(t.right);
System.out.println(t.element);
}
}
brukes på følgende binære tre?
a
/ \
/ \
b c
\ /
d e
Vi antar at den kalles med en referanse til roten i dette treet, og at variabelen "element" i hver node inneholder et enkelt tegn som i figuren.
Svar: a, b, b, d, d, d, b, a, c, e, e, e, c, c, a
[rediger]
Oppgave 10.4 && 10.5
/**
*
* @author Lars Emil
*/
public class TreNode {
int data;
TreNode venstre, hoeyre;
public TreNode(int n)
{
data = n;
venstre = hoeyre = null;
}
public int antallBlader(TreNode rot)
{
// Returnerer antall blader i et tre med en gitt rot
int antall = 0;
if(rot.venstre == null && rot.hoeyre == null)
antall++;
else
{
if(rot.venstre != null)
antall += antallBlader(rot.venstre);
if(rot.hoeyre != null)
antall += antallBlader(rot.hoeyre);
}
return antall;
}
public int antallMedEttBarn(TreNode rot)
{
// Returnerer antall noder med bare ett barn
// i et tre med en gitt rot
int antall = 0;
if(rot.venstre == null && rot.hoeyre != null)
{
antall++;
antall += antallMedEttBarn(rot.hoeyre);
}
else if(rot.venstre != null && rot.hoeyre == null)
{
antall++;
antall += antallMedEttBarn(rot.venstre);
}
else if(rot.venstre != null && rot.hoeyre != null)
{
antall += antallMedEttBarn(rot.hoeyre);
antall += antallMedEttBarn(rot.venstre);
}
return antall;
}
public int antallMedToBarn(TreNode rot)
{
// Returnerer antall noder med to barn (fulle noder)
// i et tre med en gitt rot
int antall = 0;
if(rot.venstre == null && rot.hoeyre != null)
{
antall += antallMedToBarn(rot.hoeyre);
}
else if(rot.venstre != null && rot.hoeyre == null)
{
antall += antallMedToBarn(rot.venstre);
}
else if(rot.venstre != null && rot.hoeyre != null)
{
antall ++;
antall += antallMedToBarn(rot.hoeyre);
antall += antallMedToBarn(rot.venstre);
}
return antall;
}
public int finnVerdi(TreNode rot, int verdi)
{
int help = 0;
if(rot.data == verdi)
help = rot.data;
else
{
if(rot.venstre != null)
help += finnVerdi(rot.venstre, verdi);
if(help == 0 && rot.hoeyre != null)
help += finnVerdi(rot.hoeyre, verdi);
}
return help;
}
}
/**
*
* @author Lars Emil
*/
public class TreNodeTest
{
public static void main(String[] args)
{
/* 2
* / \
* 1 3
* / \
* 5 4
* / \
* 6 7
*/
TreNode t1 = new TreNode(1);
TreNode t2 = new TreNode(2);
TreNode t3 = new TreNode(3);
TreNode t4 = new TreNode(4);
TreNode t5 = new TreNode(5);
TreNode t6 = new TreNode(6);
TreNode t7 = new TreNode(7);
t2.venstre = t1;
t2.hoeyre = t3;
t3.venstre = t5;
t3.hoeyre = t4;
t4.hoeyre = t7;
t5.venstre = t6;
System.out.println("Antall blader: " + t2.antallBlader(t2));
System.out.println("Antall Med Ett Barn: " + t2.antallMedEttBarn(t2));
System.out.println("Antall Med To Barn: " + t2.antallMedToBarn(t2));
System.out.println("Finn verdi: " + t2.finnVerdi(t2, 8));
}
}
