java二进制搜索树如何在“main”中调用我的inoder方法,并在输出中省略null?
这是我的密码:
宠物。java
package petsuppliespets;
public class Pet implements SortedADT {
private class BinarySearchTreeNode {
private Comparable object;
private BinarySearchTreeNode left;
private BinarySearchTreeNode right;
}
private BinarySearchTreeNode root;
// set by find to allow remove to work
private BinarySearchTreeNode current;
private BinarySearchTreeNode parent;
public String toString(){
String treeDetails = new String();
if (this.root != null) {
treeDetails+=this.getTree(this.root,0);
}
else{
treeDetails+="tree is empty";
}
return treeDetails;
}
private String getTree(BinarySearchTreeNode current, Integer level) {
String treeDetails = new String();
level++;
if (current != null) {
treeDetails += this.getTree(current.right, level);
for (Integer i = 0; i < level; i++) {
treeDetails += "";
}
treeDetails += current.object + "\n";
treeDetails += this.getTree(current.left, level);
} else {
for (Integer i = 0; i < level; i++) {
treeDetails += "";
}
}
return treeDetails;
}
public String getTraversals() {
String traversalsDetails = new String();
if (this.root != null) {
traversalsDetails += "in order\n";
traversalsDetails += this.getInOrder(this.root) + "\n";
traversalsDetails += "pre order\n";
traversalsDetails += this.getPreOrder(this.root) + "\n";
traversalsDetails += "post order\n";
traversalsDetails += this.getPostOrder(this.root) + "\n";
traversalsDetails += "reverse order\n";
traversalsDetails += this.getReverseOrder(this.root) + "\n";
} else {
traversalsDetails += "tree is empty";
}
return traversalsDetails;
}
private String getInOrder(BinarySearchTreeNode current) {
String inOrderDetails = new String();
if (current != null) {
inOrderDetails += this.getInOrder(current.left);
inOrderDetails += current.object + " ";
inOrderDetails += this.getInOrder(current.right);
}
return inOrderDetails;
}
private String getPreOrder(BinarySearchTreeNode current) {
String preOrderDetails = new String();
if (current != null) {
preOrderDetails += current.object + " ";
preOrderDetails += this.getPreOrder(current.left);
preOrderDetails += this.getPreOrder(current.right);
}
return preOrderDetails;
}
private String getPostOrder(BinarySearchTreeNode current) {
String postOrderDetails = new String();
if (current != null) {
postOrderDetails += this.getPostOrder(current.left);
postOrderDetails += this.getPostOrder(current.right);
postOrderDetails += current.object + " ";
}
return postOrderDetails;
}
private String getReverseOrder(BinarySearchTreeNode current) {
String reverseOrderDetails = new String();
if (current != null) {
reverseOrderDetails += this.getReverseOrder(current.right);
reverseOrderDetails += current.object + " ";
reverseOrderDetails += this.getReverseOrder(current.left);
}
return reverseOrderDetails;
}
public void insert(Comparable object) throws SortedADT.NotUniqueException {
/* Algorithm
create a new tree node
add the object to the new node
if tree is empty then
make root refer to the new node
else
insert the new node in the tree
end if
*/
BinarySearchTreeNode newNode = new BinarySearchTreeNode();
newNode.object = object;
if (this.root == null) {
this.root = newNode;
} else {
this.insert(newNode,this.root);
}
}
private void insert(BinarySearchTreeNode newNode,BinarySearchTreeNode current)
throws SortedADT.NotUniqueException{
/* Algorithm
if new object matches current object then
// attempt to add a duplicate
throw not unique exception
end if
if new object is less than the current object then
if current node does not have a left subtree then
make left of current the new node
else
insert the new node in the left subtree
end if
else
if current node does not have a right subtree then
make right of current the new node
else
insert the new node in the right subtree
end if
end if
end if
*/
if (newNode.object.compareTo(current.object) == 0)
throw new SortedADT.NotUniqueException();
if (newNode.object.compareTo(current.object) < 0) {
if (current.left == null) {
current.left = newNode;
} else {
this.insert(newNode,current.left);
}
} else if (current.right == null) {
current.right = newNode;
} else {
this.insert(newNode,current.right);
}
}
public Comparable find(Comparable object) throws SortedADT.NotFoundException {
return this.find(object,this.root);
}
private Comparable find(Comparable object, BinarySearchTreeNode current)
throws SortedADT.NotFoundException{
/* Algorithm
if node available then
if current object matches object to find then
object found
else
if object to find is less than the current object then
search the left subtree
else
search the right subtree
end if
end if
else
// object is not in the tree
throw not found exception
end if
*/
Comparable foundObject;
if (current != null) {
if (object.compareTo(current.object) == 0) {
this.current=current;
foundObject = current.object;
} else{
this.parent=current;
if (object.compareTo(current.object) < 0) {
foundObject = this.find(object,current.left);
} else {
foundObject = this.find(object,current.right);
}
}
} else{
throw new SortedADT.NotFoundException();
}
return foundObject;
}
public Comparable remove(Comparable object) throws SortedADT.NotFoundException {
// sets up parent and current
Comparable removedObject=this.find(object);
if (this.current.left == null && this.current.right == null) {
this.replaceNode(null);
} else if (this.current.left != null && this.current.right == null) {
this.replaceNode(this.current.left);
this.current.left = null;
} else if (this.current.left == null && this.current.right != null) {
this.replaceNode(this.current.right);
this.current.right = null;
} else {
this.replaceWithNextLargest(this.current, this.current, this.current.right);
}
return removedObject;
}
private void replaceNode(BinarySearchTreeNode replacement) {
/* algorithm
if current is root then
set root to replacement node
else
if current is the root of the left subtree of parent then
set parent's left subtreee to replacement node
else
set parent's right subtree to replacement node
end if
end if
set current object to null
*/
if (this.current == this.root) // removing root
{
this.root = replacement;
} else if (this.current == this.parent.left) {
this.parent.left = replacement;
} else {
this.parent.right = replacement;
}
this.current.object = null;
}
private void replaceWithNextLargest(BinarySearchTreeNode nodeForDeletion, BinarySearchTreeNode parent, BinarySearchTreeNode current) {
/* Algorithm
if current does not have a left subtree then
copy the current object into the node for deletion
if parent matches the node for deletion then
set parent's right subtree to be current's right subtree
else
set parent's left subtree to be current's right subtree
end if
clear the current node
else
replace node for deletion with the next largest in current's left subtree
end if
*/
if (current.left == null) {
nodeForDeletion.object = current.object;
if (parent == nodeForDeletion) {
parent.right = current.right;
} else {
parent.left = current.right;
}
current.object = null;
current.right = null;
} else {
this.replaceWithNextLargest(nodeForDeletion, current, current.left);
}
}
}
PetTest。java
package petsuppliespets;
public class PetTest {
public static void main(String[] args) {
SortedADT sorted = new Pet();
String pet;
Integer option;
do {
System.out.println("0: quit");
System.out.println("1: insert");
System.out.println("2: remove");
System.out.println("3: find");
System.out.println("4: show traversals");
System.out.println("5: display");
option = Input.getInteger("option: ");
switch (option) {
case 0:
System.out.println("quitting program");
break;
case 1:
pet=Input.getString("pet: ");
try{
sorted.insert(pet);
System.out.println("inserted");
}
catch(SortedADT.NotUniqueException e){
System.out.println("insert invalid - pet not unique");
}
break;
case 2:
pet=Input.getString("pet: ");
try{
pet=(String)sorted.remove(pet);
System.out.println(pet+" removed");
}
catch(SortedADT.NotFoundException e){
System.out.println("remove invalid - pet not found");
}
break;
case 3:
pet=Input.getString("pet: ");
try{
pet=(String)sorted.find(pet);
System.out.println(pet+" found");
}
catch(SortedADT.NotFoundException e){
System.out.println("pet not found");
}
break;
case 4:
// downcast as method not part of the interface
System.out.println(((Pet)sorted).getTraversals());
break;
case 5:
System.out.println(sorted);
break;
default:
System.out.println("invalid option");
}
} while (option != 0);
}
}
案例5并没有像预期的那样工作,因为我得到了如下输出
null
mouse
null
dog
null
cat
null
我想去哪里
cat
dog
mouse
我试过各种各样的东西,比如
sorted.getInOrder();
pet=(String)sorted.getInOrder(pet);
System.out.println(sorted.toString());
。。。但这些都不起作用。有什么提示吗?我知道inoorder方法是通过查看getTraversals
的输出来工作的,但我似乎不知道如何将其称为我的main方法。短暂性脑缺血发作
编辑:我做了一些小的调整,使输出更接近我想要的,但我仍然以相反的字母顺序得到列表
编辑2:我学会了如何控制字母顺序。我只需要颠倒{
共 (0) 个答案