java - pakningsproblem: - Udvikleren.dk - Programmering, webdesign og grafik

Tags: java

Bruger #13551 @ 03.04.08 21:36

Hej!

public class BinaryTreeTest {

public static void main(String[] args) {

static class Node {
Node left;

Node right;

int value;

public Node(int value) {
this.value = value;
}
}

public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) {
insert(node.left, value);
} else {
System.out.println(" Inserted " + value + " to left of "
+ node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}

Jeg har fundet det her på internettet men jeg ved ikke hvordan jeg kan f.eks. bruge disse tal 100, 50, 25 , 50 , 25 , 30 , 10 ,70 ,10 , 30 til at lave et binært træ.

Jeg skal bruge det til at pakke tallene ind I en kasse så resultatet bliver sådan her:
100 er kassens størrelse og outputet sådan her:
50 25 25
50 30 10 10
70 30

”Den ser på elementerne et for et, og pakker hvert element I den første kasse, som harp lads nok. Er der ingen af de allerede anvendte kasser som har plads til elementet, tags en ny kasse i brug.”
”Vi skal bruge et fuldstændigt binært træ. Bladet længst til venstre repræsentere den første kasse, det næste blad repræsenterer den anden kasse osv.. I hvert blad opbevares et helttal t, som angviver, hvor meget ledig plads der er i den tilsvarende kasse. I hver indre knude opbevares det største heltal, som findes i knudens undertræ.”

ER DER NOGEN DER HAR EN IDEE TIL HVORDAN JEG KAN LAVE DET! Skal jeg overhovedet bruge det stykke kode som jeg har fundet!!! eller er der en nemmere måde?

Håber at der er nogen som kan hjælpe mig på rette vej!

3 svar postet i denne tråd vises herunder
2 indlæg har modtaget i alt 6 karma

Sorter efter stemmer Sorter efter dato

Bruger #12836 @ 04.04.08 09:53

857

Hej Robert,
Jeps, det er en ganske fin implementering. Referencen til "data" er tallet "value", idet at det er et binært træ over heltal.

Hej Heidi,
Ganske glimrende implementation.

Du lægger dit træ ind i main:
Node myTree = new Node(50);
insert(myTree, 40);
insert(myTree, 60);
insert(myTree, 100);
insert(myTree, 90);

Klassen du har fundet laver dog ikke et "fuldstændigt" binært træ, idet at dybden ikke altid udvides. det som der mangler er, at træ strukturen udvides så en knude i træet indeholder det største tidligre tal, og at der samtidig udvides.

Der mangler håndtering til forandring af topknuden når der placeres til højre - samtidig skal der ved højreplacering også laves en "insert" med den gamle knude value på node.left.

Med venlig hilsen
Ieet

Bruger #5620 @ 04.04.08 11:18

1.500

Det så sikkert 4 siden sidst jeg havde noget med de hadet BST at gøre så ved ikke om dette opfylder BST.
BST.java

Kode

public class BST {
  Node root;
  public BST(){
    root=new Node();
  }
  public void print(){
    root.print();
  }
  public void insert(int value) {
    root.insert(value);
  }		
}

Node.java

Kode

public class Node {
  Node left;
  Node right;
  int value=100;
  Bucket data;
  public Node() {		
    data=new Bucket();
    data.setMax(100);
  }
  public void print(){
    if(data!=null){
      System.out.println("Print Bucket");
      data.printValues();
      System.out.println();
    }else{
      System.out.println("Inner Node(");
      if(left!=null){
        System.out.println("Left Node(");
        left.print();
        System.out.println(")");
      }
      if(right!=null){
        System.out.println("Right Node(");
        right.print();
        System.out.println(")");
      }
      System.out.println(")");
    }
  }	
  public void insert(int a_value){
    if(value>=a_value){
      if(data!=null){
        data.addValue(a_value);
        value=data.getFree();
      }else if(left!=null&&left.value>=a_value){
        left.insert(a_value);
        if(right!=null){
          value=Math.max(left.value,right.value);
        }else{
          value=left.value;
        }
      }else if(right!=null&&right.value>=a_value){
        right.insert(a_value);
        value=Math.max(right.value,left.value);		
      }
    }else{		
      Node n=new Node();
      n.left=left;
      n.right=right;
      n.value=value;
      n.data=data;
      data=null;
      left=n;
      right=new Node();
      right.insert(a_value);
      value=Math.max(left.value,right.value);
    }
  }
}

App.java

Kode

public class App {
  public static void main(String[] args) {
    Integer[] numbers = {50 , 25 , 50 , 25 , 30 , 10 , 70 , 10 , 30};	
    BST bst=new BST();
    for(int i = 0; i < numbers.length; i++) {
      bst.insert(numbers[i]);
    }
    System.out.println("BST Buckets");
    bst.print();
  }
}

Outputtet skulle gerne have en struktur(uden indrykningerne) sådan her:

Kode

Inner Node(
    Left Node(
        Inner Node(
            Left Node(
                Print Bucket
                50 25 25 
            )
            Right Node(
                Print Bucket
                50 30 10 10 
            )
        )
    )
    Right Node(
        Print Bucket
        70 30 
    )
)

Indlæg senest redigeret d. 04.04.2008 11:20 af Bruger #5620

Bruger #2695 @ 03.04.08 22:14

1.963

bob bob...ved ikke lige så meget om kassers størrelse men jeg kan da se at små tal lægges i venstre undertræ og større lægges i højre undertræ.
Det er en ganske fin implementering af et binært søgetræ men normalt ville man nok også gemme en reference til noget data i Node objektet, for tallet alene giver nok ikke så meget mening.

pakningsproblem:

Karma barometer (30 dage)

Modtaget

Givet

Favorit hos
Forum tråde
Artikler