Binary Search Tree Druckbereich

Question

Also muss ich die BST-Klasse ändern, um eine PrintRange-Funktion zu enthalten, die im Wesentlichen alle Knoten zwischen zwei Werten in der Reihenfolge drucken würde.

Hier ist die Klasse

/** Source code example for "A Practical Introduction to Data 
    Structures and Algorithm Analysis, 3rd Edition (Java)" 
    by Clifford A. Shaffer 
    Copyright 2008-2011 by Clifford A. Shaffer 
*/ 

import java.lang.Comparable; 

/** Binary Search Tree implementation for Dictionary ADT */ 
class BST<Key extends Comparable<? super Key>, E> 
     implements Dictionary<Key, E> { 
    private BSTNode<Key,E> root; // Root of the BST 
    int nodecount;    // Number of nodes in the BST 

    /** Constructor */ 
    BST() { root = null; nodecount = 0; } 

    /** Reinitialize tree */ 
    public void clear() { root = null; nodecount = 0; } 

    /** Insert a record into the tree. 
     @param k Key value of the record. 
     @param e The record to insert. */ 
    public void insert(Key k, E e) { 
    root = inserthelp(root, k, e); 
    nodecount++; 
    } 

// Return root 

    public BSTNode getRoot() 
    { 
    return root; 
    } 

/** Remove a record from the tree. 
     @param k Key value of record to remove. 
     @return The record removed, null if there is none. */ 

    public E remove(Key k) { 
    E temp = findhelp(root, k); // First find it 
    if (temp != null) { 
     root = removehelp(root, k); // Now remove it 
     nodecount--; 
    } 
    return temp; 
    } 

    /** Remove and return the root node from the dictionary. 
     @return The record removed, null if tree is empty. */ 
    public E removeAny() { 
    if (root == null) return null; 
    E temp = root.element(); 
    root = removehelp(root, root.key()); 
    nodecount--; 
    return temp; 
    } 

    /** @return Record with key value k, null if none exist. 
     @param k The key value to find. */ 
    public E find(Key k) { return findhelp(root, k); } 

    /** @return The number of records in the dictionary. */ 
    public int size() { return nodecount; } 

    private E findhelp(BSTNode<Key,E> rt, Key k) { 
    if (rt == null) return null; 
    if (rt.key().compareTo(k) > 0) 
    return findhelp(rt.left(), k); 
    else if (rt.key().compareTo(k) == 0) return rt.element(); 
    else return findhelp(rt.right(), k); 
} 
/** @return The current subtree, modified to contain 
    the new item */ 
private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt, 
            Key k, E e) { 
    if (rt == null) return new BSTNode<Key,E>(k, e); 
    if (rt.key().compareTo(k) > 0) 
    rt.setLeft(inserthelp(rt.left(), k, e)); 
    else 
    rt.setRight(inserthelp(rt.right(), k, e)); 
    return rt; 
} 
/** Remove a node with key value k 
    @return The tree with the node removed */ 

private BSTNode<Key,E> removehelp(BSTNode<Key,E> rt,Key k) { 
    if (rt == null) return null; 
    if (rt.key().compareTo(k) > 0) 
    rt.setLeft(removehelp(rt.left(), k)); 
    else if (rt.key().compareTo(k) < 0) 
    rt.setRight(removehelp(rt.right(), k)); 
    else { // Found it 
    if (rt.left() == null) return rt.right(); 
    else if (rt.right() == null) return rt.left(); 
    else { // Two children 
     BSTNode<Key,E> temp = getmin(rt.right()); 
     rt.setElement(temp.element()); 
     rt.setKey(temp.key()); 
     rt.setRight(deletemin(rt.right())); 
    } 
    } 
    return rt; 
} 

private BSTNode<Key,E> getmin(BSTNode<Key,E> rt) { 
    if (rt.left() == null) return rt; 
    return getmin(rt.left()); 
} 

private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) { 
    if (rt.left() == null) return rt.right(); 
    rt.setLeft(deletemin(rt.left())); 
    return rt; 
} 
    private void printhelp(BSTNode<Key,E> rt) { 
    if (rt == null) return; 
    printhelp(rt.left()); 
    printVisit(rt.element()); 
    printhelp(rt.right()); 
    } 

    private StringBuffer out; 

    public String toString() { 
    out = new StringBuffer(400); 
    printhelp(root); 
    return out.toString(); 
    } 
    private void printVisit(E it) { 
    out.append(it + "\n"); 
    } 

    public void printPreOrder(BSTNode<E, E> root) { 
     if (root != null) { 
      System.out.println(root.element()); 
      printPreOrder(root.left()); 
      printPreOrder(root.right()); 
     } 
    } 

    public void printInOrder(BSTNode<E, E> root) { 
     if (root != null) { 
      printInOrder(root.left()); 
      System.out.println(root.element()); 
      printInOrder(root.right()); 
     } 
    } 

    public void printPostOrder(BSTNode<E, E> root) { 
     if (root != null) { 
      printPostOrder(root.left()); 
      printPostOrder(root.right()); 
      System.out.println(root.element()); 
     } 
    } 

} 

Hier ist, was ich bisher für die Printrange-Funktion haben:

public void printRange(BSTNode<E, E> root, E low, E high) { 
      if (root != null) { 
      printRange(root.left(), low, high); 
      if (root.element().toString().compareTo(low.toString()) > 0 && root.element().toString().compareTo(high.toString()) < 0) 
       System.out.println(root.element()); 
      printRange(root.right(), low, high); 
      } 
     } 

Aber es ist mir ein Fehler geben. Irgendwelche Vorschläge, wie man Elemente/Knoten vergleicht/bin ich nicht sicher in einer BST?

Hier ist der Fahrer, wenn es

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

public class Lab8a { 

    public static void main(String[] args) { 
     BST<String, String> tree = new BST<String, String>(); 
     Scanner fileScan = null, scan = new Scanner(System.in); 

     //Open file 
     try { 
      fileScan = new Scanner(new File("inventory.txt")); 
     } catch (FileNotFoundException e) { 
      e.printStackTrace(); 
     } 

     //Reads elements from file 
     while (fileScan.hasNextLine()) { 
      String s = fileScan.nextLine(); 
      tree.insert(s, s); 
     } 

     System.out.println("\nRange"); 
     tree.printRange(tree.getRoot(), "A", "B"); 

    } 

} 

Und die Textdatei hilft:

CT16C1288B

DT14B1225F

MI15B1250A

MI15B1251A

HO03N1095A

HY07D1095BQ

KI04D2593C

DG12A1240AQ

HY03G2593BQ

TO30A1310A

HO03N1095AQ

HO01H1351C

HO01H1350C

FT18A1288B

LR15A1000A

BM12E1000A

VW02B3113A

NI23H1230AQ

LX03D2503A

LX03D2502A

LX03D2502A

VW22A3113B

VW22B3113A

Answer 1

ich mich geirrt. Es gab keinen Fehler. Ich muss den Code irgendwann korrigiert haben.