Nada

DATALOGIÖVNING 7 - BINÄRTRÄD

TRÄDBYGGEN

Hur ser det binärträd ut som skapas om man sätter in talen 4 2 1 6 3 7 5 i denna ordning? Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2? Är båda träden binära sökträd?

POSTORDERTRÄD

Skriv ut dom båda träden i "inorder" och bygg upp ett nytt träd från denna talföljd. Skriv sedan ut dom i preorder och bygg upp nya träd från dessa talföljder. Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder. Kommentera resultaten!

SPARA TRÄD I STACK

Om man i en rekursiv trädutskrift ersätter System.out.println med push, så kommer alla talen in i en stack. Om man sedan vill bygga upp samma träd från talen i stacken, bör man då ha använt inordning, preordning eller postordning vid utskriften?

RADERA HELA TRÄDET

Ett binärträd innehåller en miljon poster. Hur raderar man enklast hela trädet?

REKURSIV SÖKNING

På föreläsningen tillverkades klassen BinTree med metoderna insert, exists, write och antal. Alla utom sökmetoden exists är rekursiva. Försök nu att skriva även den rekursivt!

REKURSIV SUMMA

Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet sum(root) ger rätt svar.

REKURSIVT LÖVANTAL

Ge en rekursiv tanke för antalet löv i trädet. (Ett löv är en post utan barn.) Programmera den så att anropet antallöv(root) ger rätt svar.

REKURSIV HÖJD

Ge en rekursiv tanke för höjden av ett träd. (Höjden definieras konstigt nog som antalet nivåer -1. Ett tomt träd får höjden -1.)

Här är den kod som skrevs på föreläsningen

class Node                                               {
  int tal                                                ;
  Node left=null,right=null                              ;}
public class BinTree                                     {
  private Node root=null                                 ;
  public boolean exists(int talet)                       {
    Node p=root                                          ;
    while(p!=null)                                       {
      if(talet<p.tal) p=p.left                           ;
      else if(talet>p.tal) p=p.right                     ;
      else return true                                   ;}
    return false                                         ;}
  private void write(Node p)                             {
    if(p==null) return                                   ;
    write(p.left)                                        ;
    System.out.println(p.tal)                            ;
    write(p.right)                                       ;}
  public void write()                                    {
    write(root)                                          ;}
  private Node insert(int talet, Node p)                 {
    if(p==null)                                          {
      p=new Node()                                       ;
      p.tal=talet                                        ;
      return p                                           ;}
    if(talet<p.tal) p.left=insert(talet,p.left)          ;
    else if(talet>p.tal) p.right=insert(talet,p.right)   ;
    else System.out.println("Dubblett: "+talet)          ;
    return p                                             ;}
  public void insert(int talet)                          {
    root = insert(talet,root)                            ;}
  private int antal(Node p)                              {
    if(p==null) return 0                                 ;
    return 1+antal(p.left)+antal(p.right)                ;}
  public int antal()                                     {
    return antal(root)                                   ;}}
class TestTree                                           {
  public static void main(String[] args)                 {
  BinTree tree = new BinTree()                           ;
  while(Mio.NextChar()!='\n') tree.insert(Mio.GetInt())  ;
  tree.write()                                           ;
  System.out.println(tree.antal()+" poster")             ;
  Mio.GetLine()                                          ;
  System.out.println("Sök efter ett tal: ")              ;
  if(tree.exists(Mio.GetInt())) System.out.println("OK") ;
  else System.out.println("Fanns inte")                  ;}}

Lösningar finns här