我正在为我的数据结构类从事一项作业分配,该作业利用BST数据结构对15个具有字符串名称和Int权重值的节点进行排序。我应该为该类使用的键值是字符串名称。到目前为止,这是我的代码:
import java.util.Scanner;
/**
*
* @author daniel
*/
public class Assignment3 {
public static void main(String args[]){
Scanner keyboard = new Scanner(System.in);
Tree BST = new Tree();
//Add 15 names and weights to Tree
for(int i = 0; i < 15; i++){
Node newNode = new Node(keyboard.next(), keyboard.nextInt());
BST.insert(newNode.name);
}
System.out.print("Post: \n");
BST.postorder();
System.out.print("\nPre: \n");
BST.preorder();
System.out.print("\nIn: \n");
BST.inorder();
}
}
class Node{
Node left, right;
int weight;
String name;
//Constructors
public Node(String n){
left = null;
right = null;
name = n;
}
public Node(String n, int w){
left = null;
right = null;
name = n;
weight = w;
}
}
class Tree{
private Node root;
public Tree(){
root = null;
}
//Insertion Method
public void insert(String name){
root = insert(root, name);
}
//Insert Recursively
private Node insert(Node node, String name){
if(node == null){
node = new Node(name);
}else{
int compare = name.compareToIgnoreCase(node.name);
if(compare < 0){node.left = insert(node.left, name);}
else{node.right = insert(node.right, name);}
}
return node;
}
//Inorder Traversal
public void inorder(){inorder(root);}
public void inorder(Node current){
if(current != null){
inorder(current.left);
System.out.print(current.name + " ");
inorder(current.right);
}
}
//Postorder Traversal
public void postorder(){inorder(root);}
public void postorder(Node current){
if(current != null){
postorder(current.left);
postorder(current.right);
System.out.print(current.name + " ");
}
}
//Preorder Traversal
public void preorder(){inorder(root);}
public void preorder(Node current){
if(current != null){
System.out.print(current.name + " ");
preorder(current.left);
preorder(current.right);
}
}
}
但是,当我运行代码时,所有遍历都将按字母顺序返回值。
这是我的输入:n 1 b 2 c 3 i 4 a 5 r 6 b 7 q 8 p 9 h 10 y 11 t 12 w 13 z 14 x 15
输出:
发布:
a b b c h i n p q r t w x y z
上一个:
a b b c h i n p q r t w x y z
在:
a b b c h i n p q r t w x y z
这与我如何输入数据无关。我已经尝试过多次输入不同的数据,但是我不知道出了什么问题。我在想这与我的插入方法有关,但是我不确定从这里开始。谢谢你的帮助。
最佳答案
public void postorder(){inorder(root);} // why is this inorder(root), it should be postorder(root), change it same with preorder.
public void postorder(Node current){
if(current != null){
postorder(current.left);
postorder(current.right);
System.out.print(current.name + " ");
}
}