Avatar billede bell_c_bub Nybegynder
23. oktober 2001 - 17:44 Der er 10 kommentarer og
1 løsning

Hjælp Counter til binary trees

Jeg sidder og er igang med at løse en opgave og løber hovedet mod en mur. Problemet består i at jeg skal lave en counter til et binært træ, denne counter skal tælle højden af træet, altså ikke antallet af blade
:-(. Metoden jeg har arbejdet på hedder skrivhoejde

Vedlagt min kode:

class BTrae
{
  int hoejde = 0;
  int taeller = 0;
 
  private Node root = null;

  private class Node
  {
    int data;
    Node left, right;

    public Node(int d)
    {
      data = d;
      left = null;
      right = null;
    }   
  }     
 
  //indsæt iterativt
  public void indsaetIterativt(int nydata)
  {
          if (root == null)
          {
              root = new Node(nydata);
              return;
          }
          else
          {
              Node temp = root;
              Node følger = null;
              while (temp != null)   
              {
                  if (temp.data==nydata)
                      return;
                  følger = temp;
                  if    (nydata < temp.data)                                     
                      temp = temp.left;                 
                  else
                      temp = temp.right;                 
              }
              if (følger.data > nydata)
                  følger.left = new Node(nydata);
              else
                  følger.right = new Node(nydata);
          }
  }
 
  //public interface til inorder sortering
  public void inorder()
  {
    inorder(root);
  }
 
  private void inorder(Node trae)
  {
    if (trae!=null)
    {
      inorder(trae.left);
      System.out.print(trae.data+\"  \");
      inorder(trae.right);
    }
  }

  //public interface til preorder sortering
  public void preorder()
  {
    preorder(root);
  }

  private void preorder(Node trae)
  {
    if (trae!=null)
    {
      System.out.print(trae.data+\"  \");
      preorder(trae.left);
      preorder(trae.right);     
    }
  }
 
  //public interface til postorder sortering
  public void postorder()
  {
    postorder(root);
  }
 
  private void postorder(Node trae)
  {
    if (trae!=null)
    {
      postorder(trae.left);
      postorder(trae.right);
      System.out.print(trae.data+\"  \");
    }
  } 
  /*Her er tælleren
  */
  public void SkrivHoejde()
  {
      SkrivHoejde(root);
  }
 
 
  private void SkrivHoejde(Node trae)
  {
      System.out.println(\"taeller\"+taeller);
         
      if (trae != null)
      {
        SkrivHoejde(trae.left);
        if (trae.left != null){taeller++;}
        SkrivHoejde(trae.right);
        if (trae.right != null){taeller++;}
      }

      if (taeller > hoejde)
      {
        hoejde = taeller;
        System.out.println(\"hoejde \"+hoejde);
      }
  }
 
  public void skrivSti(int tal)
  {
    Node temp=root;
    while (temp.data!=tal)
    {
      System.out.print(temp.data+\"  \");
      if (temp.data>tal) temp=temp.left;
      else temp=temp.right;
    }
    System.out.println(temp.data);
  }
}

public class KoerBTrae
{
  public static void main(String[] args) throws Exception
  {
          BTrae bt = new BTrae();
          bt.indsaetIterativt(-1);
          bt.indsaetIterativt(10);
          bt.indsaetIterativt(-50);
          bt.indsaetIterativt(-20);
          bt.indsaetIterativt(50);
          bt.indsaetIterativt(4);
          bt.indsaetIterativt(5);
          bt.indsaetIterativt(6);
          System.out.println(\"Inorder\");
          bt.inorder();
          System.out.println();
          System.out.println(\"Preorder\");
          bt.preorder();
          System.out.println();
          System.out.println(\"Postorder\");
          bt.postorder();
          System.out.println();
          System.out.println(\"Sti til 50 (inkl.)\");
          bt.skrivSti(50);
          bt.SkrivHoejde();
  }
}
Avatar billede agony Nybegynder
23. oktober 2001 - 17:50 #1
så bliver du vel nød til at lave en Levelorder Traversal som tæller en int op for hver ny level.
Avatar billede bell_c_bub Nybegynder
23. oktober 2001 - 17:55 #2
jahhh uddyb bitte :-)
Avatar billede jakoba Nybegynder
23. oktober 2001 - 18:05 #3
private int SkrivHoejde(Node trae)
  {
      if (trae == null) return 0;
      int h,l;
      l = SkrivHoejde(trae.left);
      h = SkrivHoejde(trae.right);
      return (l > h) ? 1+l : 1+h
  }

og i din testroutine:
    System.out.println(\"taeller: \"+SkrivHoejde());

mvh JakobA
Avatar billede jakoba Nybegynder
23. oktober 2001 - 18:07 #4
ups. skulle nok snarere være:
    System.out.println(\"taeller: \"+bt.SkrivHoejde());
Avatar billede jakoba Nybegynder
23. oktober 2001 - 18:11 #5
Ups. ups.  naturligvis også:

  public int SkrivHoejde()
  {
      return SkrivHoejde(root);
  }

Avatar billede bell_c_bub Nybegynder
23. oktober 2001 - 19:30 #6
Det ser meget fint ud ... tak :-))  Men jeg tror ikke jeg er helt med på den der: return (l > h) ? 1+l : 1+h .... Altså, jeg kan godt se at den skal returnere det af de to der er højere - men hvorfor skal der være 1+l og 1+h ? (der er altså 1-tallet jeg ikke helt kan gennemskue)
 
Avatar billede frosig Nybegynder
23. oktober 2001 - 19:49 #7
Christian, så svar dog selv på dine opgaver... Du har hele dagen i morgen!
Avatar billede bell_c_bub Nybegynder
23. oktober 2001 - 19:50 #8
hvorfor dog det:-)
Avatar billede jakoba Nybegynder
23. oktober 2001 - 19:51 #9
Der lægges een til for hvert rekursionsniveau den kommer op på. det ettal er selve tælleren.
Avatar billede bell_c_bub Nybegynder
23. oktober 2001 - 19:51 #10
kan du ikke lige forklare mig hvad
return (l > h) ? 1+l : 1+h
helt præcis gør jeg er ikke lige med...
Rasmus!
Avatar billede bell_c_bub Nybegynder
23. oktober 2001 - 19:53 #11
vise ord jeg bukker mig i støvet jakoba og du får alle point og en virtuel øl :-]...
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester