Løsningsforslag for Oppgavesett 11
Fra Hiofwiki
[rediger]
Oppg.1
k
/ \
/ \
c n
/ \ \
a e s
/ \ /
d h p
1.1 Setter inn m, f, b, t, c, s i det opprinnelige treet:
-m: (k<m)(k.hoyre!=null)->(n>m)(n.venstre==null)->(n.venstre=m)
k
/ \
/ \
/ \
c n
/ \ / \
a e m s
/ \ /
d h p
-f:(k>f)(k.venstre!=null)->(c<f)(c.hoyre!=null)->(e<f)(e.hoyre!=null)->(h>f)(h.venstre==null)->(h.venstre=f)
k
/ \
/ \
/ \
c n
/ \ \
a e s
/ \ /
d h p
/
f
-b: (k>b)(k.venstre!=null)->(c>b)(c.venstre!=null)->(a<b)(a.hoyre==null)->(a.hoyre=b)
k
/ \
/ \
/ \
c n
/ \ \
/ \ \
a e s
\ / \ /
b d h p
-t: (k<t)(k.hoyre!=null)->(n<t)(n.hoyre!=null)->(s<t)(s.hoyre==null)->(s.hoyre=t)
k
/ \
/ \
/ \
c n
/ \ \
a e s
/ \ / \
d h p t
-c: (k>c)(k.venstre!=null)->(c==c)(c.hoyre!=0)->(e>c)(e.venstre!=null)->(d>c)(d.venstre==null)->(d.venstre=c)
k
/ \
/ \
/ \
c n
/ \ \
a e s
/ \ /
d h p
/
c
-s: (k<s)(k.hoyre!=null)->(n<s)(n.hoyre!=null)->(s==0)(s.hoyre==null)->(s.hoyre=s)
k
/ \
/ \
/ \
c n
/ \ \
a e s
/ \ / \
d h p s
1.2 Finner hvilke sammenligninger som blir gjort når man søker etter c, s, k, a, d, f, t:
-c: (k>c)-V>(c==c)-H>(e>c)-V>(d>c)-V>(null)
-s: (k<s)-H>(n<s)-H>(s==s)-H>(null)
-k: (k==k)-H>(n>k)-V>(null)
-a: (k>a)-V>(c>a)-V>(a==a)-H>(null)
-d: (k>d)-V>(c<d)-H>(e>d)-V>(d==d)-H>(null)
-f: (k>f)-V>(c<f)-H>(e<f)-H>(h>f)-V>(null)
-t: (k<t)-H>(n<t)-H>(s<t)-H>(null)
1.3
-
[rediger]
Oppg.2
2a
public void writeLetter(TreeNode root, int x)
{
if (root.value==x)
{
System.out.println(root.letter);
if (root.l!=null)
{
writeLetter(root.l, x);
}
}
else if (root.value<x && root.r!=null)
{
writeLetter(root.r, x);
}
else if (root.value>x && root.l!=null)
{
writeLetter(root.l, x);
}
}
2b
1. O(log N) 2. O(N)
2c
public void setSumAll(TreeNode root)
{
int tmp = 0;
if (root.l!=null)
{
setSumAll(root.l);
tmp += root.l.sum;
}
if (root.r!=null)
{
setSumAll(root.r);
tmp += root.r.sum;
}
root.sum = tmp + root.value;
}
2d
public void setParentAll(TreeNode root)
{
if (root.l!=null)
{
root.l.parent = root;
setParentAll(root.l);
}
if (root.r!=null)
{
root.r.parent = root;
setParentAll(root.r);
}
}
[rediger]
Oppg.3
package uke15;
/**
*
* @author erikeies
*/
public class TreeNodeTA
{
private int value;
private String word;
private int sum = 0;
private TreeNodeTA l;
private TreeNodeTA r;
private TreeNodeTA parent = null;
public TreeNodeTA(int value, String word, TreeNodeTA l, TreeNodeTA r)
{
setValue(value);
setWord(word);
setLeftChild(l);
setRightChild(r);
}
public TreeNodeTA(int value, String word, TreeNodeTA l, TreeNodeTA r, TreeNodeTA p)
{
setValue(value);
setWord(word);
setLeftChild(l);
setRightChild(r);
setParent(p);
}
public void setWord(String word)
{
this.word = word;
}
public void setSum(int sum)
{
this.sum = sum;
}
public void setValue(int value)
{
this.value = value;
}
public void setParent(TreeNodeTA parent)
{
this.parent = parent;
}
public void setLeftChild(TreeNodeTA l)
{
this.l = l;
}
public void setRightChild(TreeNodeTA r)
{
this.r = r;
}
public int getValue()
{
return value;
}
public int getSum()
{
return sum;
}
public String getWord()
{
return word;
}
public TreeNodeTA getLeftChild()
{
return l;
}
public TreeNodeTA getRightChild()
{
return r;
}
public TreeNodeTA getParent()
{
return parent;
}
public void writeWord(TreeNodeTA root, int x)
{
if (root.value==x)
{
System.out.println(root.word);
if (root.l!=null)
{
writeWord(root.l, x);
}
}
else if (root.value<x && root.r!=null)
{
writeWord(root.r, x);
}
else if (root.value>x && root.l!=null)
{
writeWord(root.l, x);
}
}
public void setSumAll(TreeNodeTA root)
{
int tmp = 0;
if (root.l!=null)
{
setSumAll(root.l);
tmp += root.l.sum;
}
if (root.r!=null)
{
setSumAll(root.r);
tmp += root.r.sum;
}
root.sum = tmp + root.value;
}
public void setParentAll(TreeNodeTA root)
{
if (root.l!=null)
{
root.l.parent = root;
setParentAll(root.l);
}
if (root.r!=null)
{
root.r.parent = root;
setParentAll(root.r);
}
}
public void addElement(String s)
{
if (s.equals(this.getWord()))
{
this.setValue(this.getValue()+1);
}
else if (s.compareTo(this.getWord())<0)
{
if (this.getLeftChild()!=null)
{
this.getLeftChild().addElement(s);
}
else
{
this.setLeftChild(new TreeNodeTA(1, s, null, null, this));
}
}
else
{
if (this.getRightChild()!=null)
{
this.getRightChild().addElement(s);
}
else
{
this.setRightChild(new TreeNodeTA(1, s, null, null, this));
}
}
}
public void inorderTraverse()
{
if (this.getLeftChild()!=null)
{
this.getLeftChild().inorderTraverse();
}
System.out.println(this.getWord() + " : " + this.getValue());
if (this.getRightChild()!=null)
{
this.getRightChild().inorderTraverse();
}
}
}
package uke15;
/**
*
* @author erikeies
*/
import java.io.*;
import java.util.*;
public class TextAnalyzer
{
public static void main(String[] args)
{
try
{
BufferedReader br = new BufferedReader(new FileReader(new File("D:\\misc\\zelda.txt")));
String text = "";
String line = "";
while ((line = br.readLine())!=null)
{
text += line + " ";
}
br.close();
text = text.toLowerCase();
/*
System.out.println(text);
*/
String[] tmp = text.split("[^a-zA-Z]");
/*
for (String word : tmp)
{
System.out.println(word);
}
*/
TreeNodeTA root = new TreeNodeTA(0, tmp[0], null, null);
for (String word : tmp)
{
if (!word.equals(""))
{
root.addElement(word);
}
}
root.inorderTraverse();
}
catch (IOException ioe)
{
System.err.println(ioe.getMessage());
}
}
}
