Nada

LÖSNING TILL DATALOGIÖVNING 7


TRÄDBYGGEN

Båda träden är binära sökträd. Det finns massor, men man vill ju helst att trädet ska vara balanserat.
               4                                  5
        2            6          och        3              7
     
    1      3      5      7             1       4       6

                                         2

POSTORDERTRÄD

Inorder: 1234567 på båda => en tarm ner åt höger
Preorder: 4231657, 5312476 => samma träd tillbaka
Postorder:1325764, 2143675 => nya konstiga träd

SPARA TRÄD I STACK

Postorder ger samma träd tillbaka, det ser man i ett exempel.

RADERA HELA TRÄDET

root=null gör att den automatiska skräpsamlingen så småningom raderar hela trädet.

REKURSIV SUMMA

Summan av talen i trädet = summan av talen i vänsterträdet + summan av talen i högerträdet + rottalet...
...men i ett tomt träd är summan noll.
int sum(Node p)                        { // sum(root) ger summan
  if(p==null) return 0                 ;
  return sum(p.left)+sum(p.right)+p.tal;}

REKURSIV SÖKNING

Att talet existerar i trädet innebär antingen att talet är mindre än rottalet och finns i vänstertädet eller att det är större än rottalet och finns i högerträdet eller att det är lika med rottalet...
...men i ett tomt träd finns inga tal.
private boolean exists(int talet, Node p)     { //anropas bara internt
  if(p==null) return false                    ;
  if(talet<p.tal) return exists(talet,p.left) ;
  if(talet>p.tal) return exists(talet,p.right);
  return true                                 ;}
public boolean exists(talet)                  { //anropas utifrån
  return exists(talet,root)                   ;}

REKURSIVT LÖVANTAL

Antal löv i trädet = antal löv i vänsterträdet + antal löv i högerträdet...
...men en ensam rotpost är ett löv
...men ett tomt träd har noll löv.
int noOfLeaves(Node p)                         {
  if(p==null) return 0                         ;
  if(p.left==null&&p.right==null) return 1     ;
  return noOfLeaves(p.left)+noOfLeaves(p.right);}

REKURSIV HÖJD

Höjden för hela trädet är höjden för det högsta av dom båda underträden plus 1 ...
...men tomt träd har höjden -1.
int height(Node p)       {
  if(p==null) return -1  ;
  int h1=height(p.left)  ;
  int h2=height(p.right) ;
  if(h1<h2) return h2+1  ;
  return h1+1            ;}