binärer Suchbaum

Question

Hallo Ich habe eine Array-Liste, die einige Zahlen darin wie {23,16,45,26,2,5,9} hat, und ich möchte einen binären Suchbaum mit dieser Array-Liste machen, die "array" und seine Elemente sind Objekte, die 2 Felder hat, 1)digit2)level aber hier möchte ich nur sein digit field.Auch dList ist ein DoublyLinkedList. das ist mein Code, aber es wird eine Ausnahme werfen. Bitte helfen Sie mir, danke.

private void method(ArrayList<Element> array) { 
    DNode header = new DNode(null, null, null); 
    DNode trailer = new DNode(null, header, null); 
    header.next = trailer; 
    DNode node = new DNode(array.get(0), header, trailer); 
    dList.addLast(node); 
    header = node 
    for(int i = 1;i<array.size();i++){ 
    makeBST(node, array.get(i)); 
    } 
} 

private void makeBST(DNode node, Element e) { 

    if (!e.equals(node.getElement())) { 
     DNode nodeOne = new DNode(e, null, null); 
     if (node.getElement().getDigit() > e.getDigit()) { 
      node.prev = nodeOne; 
     } else if (node.getElement().getDigit() < e.getDigit()) { 
      node.next = node; 
     } 
    } 
    if (e.getDigit() < node.getElement().getDigit()) { 
     makeBST(node.prev, e); 
    } 
    makeBST(node.next, e); 
} 

Ausnahme:

Exception in thread "main" java.lang.StackOverflowError 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:43) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 
    at OBST.GreedyVersion.makeBST(GreedyVersion.java:54) 

die erste Zeile der Ausnahme für diese Codezeile:

if (!e.equals(node.getElement())) 

Answer 1

Ihre rekursive Methode "private void makeBST (dnode Knoten, Element e)" benötigt eine Art Endbedingung (ein Fließpfad, der verhindert, dass er sich selbst aufruft); so wie es ist, ruft es sich rekursiv auf, was den Stack-Überlauffehler verursacht.

Answer 2

Sie haben einen StackOverflowError, der auf einen unendlichen (gut, möglicherweise zumindest) Rekursionsfehler hinweist.

p.s. Warum verwenden Sie nicht einfach TreeMap<K,V>, wobei K der Index Ihrer Daten und V der Datenwert ist?

Answer 3

Der Code ist im Grunde:

private void makeBST(DNode node, Element e) { 
    // ... (the rest of your code) 
    makeBST(node.next, e); 
} 

Es ist fast gleichbedeutend mit:

private void makeBST(DNode node, Element e) { 
    while(true) { 
     // ... (the rest of your code) 
     node = node.next; 
    } 
} 

Sie haben gerade eine Endlosschleife (aber nicht mit Weile, aber mit Rekursion). Da die Stackgröße sehr begrenzt ist, erhalten Sie nach einigen Iterationen StackOverflowError.

Aber wie auch immer, wenn es nur ein pädagogisches Experiment ist, ist es in Ordnung. Wenn Sie nur eine funktionierende BST benötigen, verwenden Sie java.util.TreeSet oder java.util.TreeMap.

Answer 4

Ich kann sehen, dass Sie versuchen, aber Sie sind ein langer Weg von der Lösung.

Sie verwenden Rekursion, also brauchen Sie einen Anhaltefall ... den Sie nicht haben.

Sie sollten auch wahrscheinlich if ... else if ... eher als das, was Sie bekommen haben (wenn ... wenn ...)

Diese Linie if (!e.equals(node.getElement())) { entweder keinen Sinn macht ...

Schauen Sie sich die Wikipedia-Artikel über binäre Bäume und binäre Suchbäume ... wird wahrscheinlich helfen.