0
所以我必須修改BST類以包含PrintRange函數,該函數將按順序在兩個值之間打印所有節點。二進制搜索樹打印範圍
這裏是類
/** 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());
}
}
}
這裏是我迄今爲止的PrintRange功能:
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);
}
}
但它給我一個錯誤。任何關於如何比較元素/節點的建議/我甚至不確定在BST中?
這裏的司機,如果有幫助
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");
}
}
而且文本文件:
CT16C1288B
DT14B1225F
MI15B1250A
MI15B1251A
HO03N1095A
HY07D1095BQ
KI04D2593C
DG12A1240AQ
HY03G2593BQ
TO30A1310A
HO03N1095AQ
HO01H1351C
HO01H1350C
FT18A1288B
LR15A1000A
BM12E1000A
VW02B3113A
NI23H1230AQ
LX03D2503A
LX03D2502A
LX03D2502A
VW22A3113B
VW22B3113A
您收到錯誤的原因是您的代碼錯誤。如果您需要關於代碼錯誤的更多具體信息,請提供有關錯誤的更多具體信息,而不僅僅是「它給我一個錯誤」。我們無法解決這個問題。 – ajb
我發現了這個錯誤。沒有。抱歉。 –