Träd uppgifter: maxDepth() och pre()

I denna sida har av utrymmesskäl endast metoderna som utökar klasserna Node1 och Tree1 visats. De fullständiga klasserna finns här: Node1 och Tree1.

Vår uppgift var att utöka klassen Tree1 med en metod int maxDepth(). Metoden returnerar det maximala djupet (avståndet mellan rot och löv) i trädet. Den anropar sig själv tills det nuvarande elementet saknar efterföljare. Om elementet har efterföljare kollar den dock om eftervarande element har efterföljare. och returnerar till slut det högsta antalet "löv".



  public int maxDepth() {
    int x1=0;
    int x2=0;
    if (left().isEmpty() && right().isEmpty()) return 1;
    if (!right().isEmpty()){
       x1=1 + right().maxDepth();
    }
    if (!left().isEmpty()){
       x2=1 + left().maxDepth();
    }
    if (x1>=x2){
       return x1;
    }
    return x2;
  }

Klassen Node1 utökades med nedstående två klasser, den första ,addLast(), adderar ett element i slutet av en lista istället för i början, och den andra ,addTwo(), sätter ihop två listor med hjälp av addLast().



   public Node1 addLast(int el) {
      if (isEmpty()) {
         Node1 l=new Node1();
         Node1 x=new Node1(el,l);
         return x;
      }
      return new Node1(first(),rest().addLast(el));
   }

   public Node1 addTwo(Node1 l) {
      if (l.isEmpty()) return this;
      return this.addLast(l.first()).addTwo(l.rest());
   }

Denna metod i Tree1 sätter ett träd i en lista genom att genomlöpa elementen i trädet i preorder-ordning. Den sätter nodens värde först i listan med hjälp av concat() på den lista som skapas av elementen i den vänstra "grenen", och denna lista sätts ihop med den högra grenens elementlista, med hjälp av funktionen addTwo().


  public Node1 pre() {
    if (isEmpty())
      return new Node1();
    return left().pre().concat(info()).addTwo(right().pre());
  }

Tillbaks till huvudsidan

email: Alireza.Niai_nouri.2077@student.uu.se