Binært Søge-Træ (BST) opgave

 

Opgave 1.

Indsæt følgende værdier i et BST i nævnte rækkefølge:
   47, 22, 68, 9, 33, 53, 88, 5, 17, 29, 46, 48
  
 

Opgave 2.

 Indsæt følgende værdier i et BST i nævnte rækkefølge:
   33, 29, 46, 22, 17, 47, 48, 53, 9, 68, 88, 5

 

Opgave 3.

 Indsæt følgende værdier i et BST i nævnte rækkefølge:
   5, 9, 17, 22, 29, 33, 46, 47, 48, 53, 68, 88
     
Hvilke konklusioner kan du udlede af ovenstående.

 

Opgave 4.

 Implementer dit eget BST.
 Du skal ikke gøre det generisk (<T>), men de data som skal indeholdes i BSTet skal kunne sammenlignes (de skal være "comparable").
Prøv at implementer indsæt-metoden rekursivt.
Udover "insert" skal du implementere "Search", Inorder", Preorder", "Postorder", benyt rekursion så ofte som det er muligt.
Prøv også at implementere "Delete"
  
Tip: Selve træ-klassen er egentlig blot adgang til roden (samt træ-metoder), det væsentlige er faktisk node-klassen (som kan være en "inner class" i BST-klassen).
 

Binary Expression-Tree (BET)

Et "Binary Expression Tree" (BET - binært udtryks-træ) indeholder elementerne til et, f.eks. algebraisk, udtryk.
F.eks. udtrykker nedenstående træ hvis man udskriver det inorder: ((a / b) + ((c - d) * e)) - bemærk at parenteser normalt sættes omkring hvert "sub-træ udtryk".
  Også preorder og postorder udskrivninger vil give mening alt efter hvordan indholdet behandles.
a, b, c, d og e vil naturligvis repræsentere tal-værdier i en given sammenhæng.

Hvis træet udskrives preorder til en tekst-fil hvor hver node skrives på en linie og der udskrives "null" for en tom subtræ-reference vil filen se ud som nedenfor:

 

+ / a null null b null null * - c null null d null null e null null

Følgende metode (i pseudo-kode) vil kunne indlæse en sådan fil i et BET:

 

public Binær_node Indlæs_BET(fil) {    data = Læs linie fra fil    Hvis data != "null" så    {   Binær_node left = Indlæs_BET(fil)        Binær_node right = Indlæs_BET(fil)        return new Binær_node(data, left, right)    } else    return null }

Opgave 1.
Udarbejd et BET som forbindes med en tekstfil via en konstruktør. Filens indhold indlæses og det tilhørende regne-udtryks resultat skal kunne returneres af en metode. ToString() metoden skal returnere udtrykket som streng - gerne med tilhørende parenteser som beskrevet ovenfor.