Gruppe 4 oppgaesett 9
Fra Hiofwiki
Oppgaver til uke 14 -- (binære) Trær
Innhold |
Oppgave 1
Følgende binære tre er gitt:
A
/ \
B C
/ \ \
/ \ \
/ \ \
D E F
/ \ / \ \
G H I J K
/ \
L M
a) Hvilken node er rotnoden? Rot noden er den noden uten foreldre, ergo A
b) Hvilke noder er blader i treet? Noder som er blader er de som ikke har noen barn, ergo G, H, L, M, J, K
c) Hva er dybden til treet? De dypeste nodene er L og M disse har en dybde på 4 nivåer
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, K, F, C
Postorder : G, H, D, L, M, I, J, E, B, K, F, C, A
bredde-først : A, B, C, D, E, F, G, H, I, J, K, L, M
Oppgave 2
Følgende binære tre er gitt:
A
/ \
B C
/ \ \
/ \ \
/ \ \
D E F
/ \ / \ \
G H I J K
/ \
L M
Angi, for hver node i dette treet:
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 noden)
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
Oppgave 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
Oppgave 4
Nodene i et binært tre inneholder bare et enkelt heltall, samt referanser til høyre og venstre barn:
class treNode
{
public treNode(int n)
{
data = n;
venstre = hoeyre = null;
}
int data;
treNode venstre, hoeyre;
}
Programmer følgende rekursive metoder:
int antallBlader(treNode rot)
{
// Returnerer antall blader i et tre med en gitt rot
}
int antallMedEttBarn(treNode rot)
{
// Returnerer antall noder med bare ett barn
// i et tre med en gitt rot
}
int antallMedToBarn(treNode rot)
{
// Returnerer antall noder med to barn (fulle noder)
// i et tre med en gitt rot
}
Lag også et lite testprogram som sjekker at metodene fungerer.
Forandret treNode til å inneholde metodene nevn over
package Oppgavesett14;
class treNode {
public treNode(int n) {
data = n;
venstre = hoeyre = null;
}
int data;
treNode venstre, hoeyre;
int antallNoder(treNode rot){
// Returnerer antall noder i et (sub)tre med en gitt rot
int antall = 1;
if (rot.venstre != null) antall += antallNoder(rot.venstre);
if (rot.hoeyre != null) antall += antallNoder(rot.hoeyre);
return antall;
}
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++;
if (rot.venstre != null) antall += antallBlader(rot.venstre);
if (rot.hoeyre != null) antall += antallBlader(rot.hoeyre);
return antall;
}
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++;
if (rot.venstre != null && rot.hoeyre == null) antall++;
if (rot.venstre != null) antall += antallMedEttBarn(rot.venstre);
if (rot.hoeyre != null) antall += antallMedEttBarn(rot.hoeyre);
return antall;
}
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++;
if (rot.venstre != null) antall += antallMedEttBarn(rot.venstre);
if (rot.hoeyre != null) antall += antallMedEttBarn(rot.hoeyre);
return antall;
}
public void mysteryPrint(treNode t)
{
if (t != null)
{
System.out.println(t.data);
mysteryPrint(t.venstre);
System.out.println(t.data);
mysteryPrint(t.hoeyre);
System.out.println(t.data);
}
}
}
Lagde så testprogrammet
package Oppgavesett14;
public class testTreNode {
public static void main(String[] args) {
/*
* 10
* / \
* / \
* / \
* 20 30
* / \ / \
* 40 50 60 70
* / \
* 80 90
*
* */
treNode t1 = new treNode(10);
treNode t2 = new treNode(20);
treNode t3 = new treNode(30);
treNode t4 = new treNode(40);
treNode t5 = new treNode(50);
treNode t6 = new treNode(60);
treNode t7 = new treNode(70);
treNode t8 = new treNode(80);
treNode t9 = new treNode(90);
t1.venstre = t2;
t1.hoeyre = t3;
t2.venstre = t4;
t2.hoeyre = t5;
t3.venstre = t6;
t3.hoeyre = t7;
t6.venstre = t8;
t7.hoeyre = t9;
System.out.println("(t1) antall blader - "+t1.antallBlader(t1));
System.out.println("(t2) antall blader - "+t1.antallBlader(t2));
System.out.println("(t3) antall blader - "+t1.antallBlader(t3));
System.out.println("(t6) antall blader - "+t1.antallBlader(t6));
System.out.println("(t1) med ett barn - "+t1.antallMedEttBarn(t1));
System.out.println("(t2) med ett barn - "+t1.antallMedEttBarn(t2));
System.out.println("(t3) med ett barn - "+t1.antallMedEttBarn(t3));
System.out.println("(t6) med ett barn - "+t1.antallMedEttBarn(t6));
System.out.println("(t1) med to barn - "+t1.antallMedToBarn(t1));
System.out.println("(t2) med to barn - "+t1.antallMedToBarn(t2));
System.out.println("(t3) med to barn - "+t1.antallMedToBarn(t3));
System.out.println("(t6) med to barn - "+t1.antallMedToBarn(t6));
}
}
Oppgave 5 - Søking i usorterte binære trær
Skriv en funksjon som finner og returnerer en bestemt verdi i et binært tre. Bruk samme klasse for nodene i treet som i oppgaven ovenfor.
treNode finnNode(treNode rot, int verdi){
// Finner og returnerer en bestemt verdi i et binært tre
treNode funnet = null;
treNode tmp = null;
System.out.println("Sjekker "+rot.data+" "+(rot.data==verdi));
if (rot.data==verdi) return rot;
else {
if (rot.venstre != null) tmp = finnNode(rot.venstre, verdi);
if (tmp != null) funnet = tmp;
if (rot.hoeyre != null) tmp = finnNode(rot.hoeyre, verdi);
if (tmp != null) funnet = tmp;
}
return funnet;
}
Dette er et eksempel på søking etter en verdi i et tre som ikke er ordnet. Hva er arbeidsmengden til denne funksjonen for et binært tre med n noder? Spiller det i dette tilfellet noen rolle om treet er balansert eller ikke, d.v.s. har høyden til treet noen betydning for arbeidsmengden? Arbeidsmengden er O(n), høyden av treet har ingen betydning for arbeidsmengden.
Oppgave 6* - En merkelig representasjon av et tre
(Denne oppgaven er kun for nerdene, det kreves ikke at arbeidsgruppene besvarer denne). Et tre er representert med noder, som er definert slik:
class treNode
{
// Konstruktør
public treNode(Object O)...
// Datafelt Object data;
// Referanser
treNode forgjenger, neste;
int hoeyde, nivaa;
}
Referansen forgjenger representerer her selve trestrukturen og peker i hver node til foreldernoden. I roten av treet er denne referansen lik null. Variabelen neste kjeder alle nodene i treet sammen i en lenket liste, i en eller annen tilfeldig rekkefølge. Starten av denne listen kan vi tenke oss er representert med en referansevariabel treNode liste I utgangspunktet er de to heltallsvariablene hoeyde og nivaa lik null i alle noder. 1.Tegn et eksempel på hvordan denne datastrukturen for et tre kan se ut for følgende binære tre:
A / \ B C / \ \ D E F
2.Høyden til en node er her definert på samme måte som i læreboka Skriv en ikke-rekursiv funksjon som setter inn høyden riktig for alle nodene i en liste som representerer et tre. 3.Skriv en funksjon som setter inn både hoeyde og nivaa riktig i alle nodene. Her kan det brukes en rekursiv funksjon i tillegg.
