英文:
How do I put my output print the keywords* in alphabetical order (abc) instead of backwards(zyx)? This is a binary search tree implementation in java
问题
class bst{
Node root; // a Node object
public class Node{
String keyword;
Record record;
int size; //number of keywords
Node l; //left node
Node r; //right node
private Node(String k){
// TODO 实例化一个具有关键字 k 的新节点。
keyword = k;
}
private void update(Record r){
//TODO 将 Record r 添加到记录链表中。您不必检查记录是否已经在列表中。
//HINT：将 Record r 添加到您的链表的前面。
if(this.record==null) {
this.record = r;
}
else {
r.next = this.record; // 新记录将放在下一个节点
this.record = r;
}
}
public boolean contains(Node curr) {
// TODO 自动生成的方法存根
return false;
}
} // 节点类结束
// 返回到bst类
public bst(){
this.root = null; // bst 根节点不连接到任何内容
}
public void insert(String keyword, FileData fd){
Record recordToAdd = new Record(fd.id, fd.author, fd.title, null);
//TODO 编写一个递归插入函数，将 recordToAdd 添加到与关键字相关联的节点记录列表中。
// 如果没有节点，则此代码应添加节点。
if(root==null) { // root 来自 node 类
root = new Node(keyword);
root.update(recordToAdd);
}
else {// 如果有一个节点，开始插入，调用 insertHelp 函数
insertHelp(keyword, recordToAdd, root);
}
}
private Node insertHelp(String keyword, Record recordToAdd, Node nObj) {
if(nObj.keyword.equals(keyword)) {
nObj.update(recordToAdd);
return nObj;
}
// 插入节点到左侧
else if(nObj.keyword.compareTo(keyword)<0) {
if(nObj.l==null) { // 如果为空，创建左节点
nObj.l = new Node(keyword);
nObj.l.update(recordToAdd);
return nObj.l;
}
else { // 否则继续插入到左侧
return insertHelp(keyword,recordToAdd, nObj.l);
}
}
// 插入节点到右侧
else if(nObj.keyword.compareTo(keyword)>0) {
if(nObj.r==null) { // 如果为空，创建右节点
nObj.r = new Node(keyword);
nObj.r.update(recordToAdd);
return nObj.r;
}
else { // 否则继续插入到右侧
return insertHelp(keyword,recordToAdd, nObj.r);
}
}
return null; // 什么都不做
}
public boolean contains(String keyword){
//TODO 编写一个递归函数，如果bst中存在特定关键字，则返回 true
// 如果根节点不存在
if(this.root==null) {
return false;
}
// 如果根节点存在，则开始查找其他节点
else {
Node help = containsHelp(root,keyword);
if(help==null) { // 如果节点未找到，则返回 false
return false;
}
else { // 如果找到，则返回 true
return true;
}
}
}
private Node containsHelp( Node nObj,String keyword) {
if(nObj.keyword.contentEquals(keyword)) {
return nObj;
}
// 如果bst的左侧存在
else if(nObj.keyword.compareTo(keyword)<0) {
return containsHelp( nObj.l,keyword);
}
// 如果bst的右侧存在
else if(nObj.keyword.compareTo(keyword)>0) {
return containsHelp( nObj.r,keyword);
}
return null; // 什么都不做
}
public Record get_records(String keyword){
//TODO 返回特定关键字的第一条记录。该记录将链接到其他记录
// 如果bst中没有关键字，则应返回 null。
if(root==null) {
return null;
}
else {
return containsHelp(root,keyword).record;
}
}
public void delete(String keyword){
//TODO 编写一个递归函数，它从二叉搜索树中删除具有关键字的节点。
// 不能使用延迟删除，如果bst中没有关键字，则该函数不应执行任何操作。
root = deleteHelp(keyword,root);// 节点根
}
public Node deleteHelp(String keyword, Node nRoot) {
// 用于存储当前节点的父节点的指针
Node parent = null;
// 从根节点开始
Node curr = nRoot;
// 在BST中搜索关键字并设置其父指针
while(curr != null && curr.keyword.compareTo(keyword)!= 0 ){
// 更新父节点为当前节点
parent = curr;
// 如果给定的键小于当前节点，则转到左子树
if(keyword.compareTo(curr.keyword)< 0){
curr = parent.l;
}// 否则转到右子树
else{
curr = parent.r;
}
} // 搜索结束
// 如果在树中未找到关键字
if(curr ==null) {
return nRoot;
}
// 情况1：如果节点没有任何子节点，删除该节点
if(curr.l==null&&curr.r==null) {
if(curr!=nRoot) {
// 如果要删除的节点不是根节点，那么设置其父节点的左/右子节点为空
if(parent.l==curr) {
parent.l=null;
}
else {
parent.r=null;
}
}
// 如果树中只有一个节点，则删除它并将根节点设置为 null
else {
nRoot=null;
}
}
// 情况2：要删除的节点有2个子节点
else if(curr.l!=null && curr.r!=null) {
// 找到其中序后继节点
Node successor=minKey(curr.r);
deleteHelp(keyword,successor); // 递归删除后继节点
curr = successor; // 将当前节点复制为后继节点。
}
// 情况3：要删除的节点只有一个子节点
else {
// 找到子节点
Node child=(curr.l!=null)?curr.l:curr.r;
// 如果要删除的节点不是
<details>
<summary>英文:</summary>
class bst{
Node root; // a Node object
public class Node{
String keyword;
Record record;
int size; //number of keywords
Node l; //left node
Node r; //right node
private Node(String k){
// TODO Instantialize a new Node with keyword k.
keyword = k;
}
private void update(Record r){
//TODO Adds the Record r to the linked list of records. You do not have to check if the record is already in the list.
//HINT: Add the Record r to the front of your linked list.
if(this.record==null) {
this.record = r;
}
else {
r.next = this.record;// the new record will be placed to the next node
this.record = r;
}
}
public boolean contains(Node curr) {
// TODO Auto-generated method stub
return false;
}
} // end of node class
// back to bst class
public bst(){
this.root = null; //the bst root is not connected to anything
}
public void insert(String keyword, FileData fd){
Record recordToAdd = new Record(fd.id, fd.author, fd.title, null);
//TODO Write a recursive insertion that adds recordToAdd to the list of records for the node associated
//with keyword. If there is no node, this code should add the node.
if(root==null) { // root is from node class
root = new Node(keyword);
root.update(recordToAdd);
}
else {// if there is a node, start inserting, call the insert help function
insertHelp(keyword, recordToAdd, root);
}
}
private Node insertHelp(String keyword, Record recordToAdd, Node nObj) {
if(nObj.keyword.equals(keyword)) {
nObj.update(recordToAdd);
return nObj;
}
// inserting node to the left
else if(nObj.keyword.compareTo(keyword)<0) {
if(nObj.l==null) { // if it is empty, create a left node
nObj.l = new Node(keyword);
nObj.l.update(recordToAdd);
return nObj.l;
}
else { // otherwise keep on inserting to the left
return insertHelp(keyword,recordToAdd, nObj.l);
}
}
//inserting node to the right
else if(nObj.keyword.compareTo(keyword)>0) {
if(nObj.r==null) { // if it is empty, create a right node
nObj.r = new Node(keyword);
nObj.r.update(recordToAdd);
return nObj.r;
}
else { // otherwise keep on inserting to the right
return insertHelp(keyword,recordToAdd, nObj.r);
}
}
return null;// do nothing
}
public boolean contains(String keyword){
//TODO Write a recursive function which returns true if a particular keyword exists in the bst
//if the root does not exist
if(this.root==null) {
return false;
}
//if the root exists, then it starts to look for other nodes
else {
Node help = containsHelp(root,keyword);
if(help==null) { // if the node isn't found, return false
return false;
}
else { // if found, return true
return true;
}
}
}
private Node containsHelp( Node nObj,String keyword) {
if(nObj.keyword.contentEquals(keyword)) {
return nObj;
}
// if the left side of bst exists
else if(nObj.keyword.compareTo(keyword)<0) {
return containsHelp( nObj.l,keyword);
}
//if the right side of bst exists
else if(nObj.keyword.compareTo(keyword)>0) {
return containsHelp( nObj.r,keyword);
}
return null; // do nothing
}
public Record get_records(String keyword){
//TODO Returns the first record for a particular keyword. This record will link to other records
//If the keyword is not in the bst, it should return null.
if(root==null) {
return null;
}
else {
return containsHelp(root,keyword).record;
}
}
public void delete(String keyword){
//TODO Write a recursive function which removes the Node with keyword from the binary search tree.
//You may not use lazy deletion and if the keyword is not in the bst, the function should do nothing.
root = deleteHelp(keyword,root);//node root
}
public Node deleteHelp(String keyword, Node nRoot) {
//pointer to store parent node of current node
Node parent = null;
//start with root node
Node curr = nRoot;
//search keyword in BST and set its parent pointer
while(curr != null && curr.keyword.compareTo(keyword)!= 0 ){
//update parent node as current node
parent = curr;
//if given key is less than the current node, go to left subtree
if(keyword.compareTo(curr.keyword)< 0){
curr = parent.l;
}//else go to the right subtree
else{
curr = parent.r;
}
} //end of search
//if keyword isn't found in the tree
if(curr ==null) {
return nRoot;
}
//case 1: if the node does not have any children, delete
// as known as leaf node
if(curr.l==null&&curr.r==null) {
if(curr!=nRoot) {
//if node to be deleted is not a root node, then set
//its parent left/right child to null
if(parent.l==curr) {
parent.l=null;
}
else {
parent.r=null;
}
}
//if tree has only one node, delete it and set root to null
else {
nRoot=null;
}
}
//case 2: node to be deleted has 2 children
else if(curr.l!=null && curr.r!=null) {
// find its in-order successor node
Node successor=minKey(curr.r);
deleteHelp(keyword,successor); //delete the successor node recursively
curr = successor; //copy current node into the successor.
}
//case 3: node to be deleted has only one child
else {
//find child node
Node child=(curr.l!=null)?curr.l:curr.r;
// if node to be deleted is not a root node. then set its parent
//to its child
if(curr!=nRoot) {
if(curr==parent.l) {
parent.l=child;
}
else {
parent.r=child;
}
}
else {
nRoot = child;
// nRoot = null;
}
}
//if node to be deleted is root node, then set the root to child
return nRoot;
}
// help function to find min value node in subtree rooted at curr
public Node minKey(Node curr) {
while(curr.l!=null) {
curr=curr.l;
}
return curr;
}
public void print(){
print(root);
}
private void print(Node t){
if (t!=null){
print(t.l);
System.out.println("***************************");
System.out.println(t.keyword);
Record r = t.record;
while(r != null){
System.out.printf("\t%s\n",r.title);
r = r.next;
}
print(t.r);
}
}
}
//here is my output:
Wesley Chu*
Knowledge-Based Image Retrieval with Spatial and Temporal Constraints
weighting*
Dan Aha
triangle-inequality*
Andy Berman
Andy Berman
John Barros
time-related
Joseph Han
temporal
Wesley Chu
spatial
Maria Ester
Wesley Chu
similarity
Andy Berman
John Barros
Ricardo Baeza-Yates
search
James Bach
relational
Chris Brunk
Joseph Han
region-based
Chuck Carson
recognition
Mauro Costa
Yi Li
query-trees
Ricardo Baeza-Yates
query-by-example
Paul Kelly
queries
Dave Angluin
pruning
Andy Berman
pose
Mauro Costa
neural-networks
Wayne Bunt
Yosama Mustafa
multimedia
Chris Faloutsos
medical
Wesley Chu
Paul Kelly
John Anderson
matching
Mauro Costa
Ricardo Baeza-Yates
lines
Yi Li
learning
Jaime Carbonell
Wayne Bunt
Wayne Bunt
Chris Brunk
Tom Huang
Dave Angluin
Dan Aha
Dan Aha
Dan Aha
Yosama Mustafa
Joan Catlett
knowledge
Joseph Han
Wesley Chu
instance-based
Dan Aha
instance-based
Dan Aha
information-retrieval
Jaime Carbonell
indexing
Mauro Costa
image-stack
Alfonso Cardenas
image-retrieval
Tom Huang
Wesley Chu
Alfonso Cardenas
Chuck Carson
Andy Berman
Andy Berman
John Barros
James Bach
Paul Kelly
John Anderson
image-management
James Bach
image-display
Alfonso Cardenas
distance-measures
Andy Berman
database
Greg Hulten
Joseph Han
Joseph Han
Soha Guha
Chris Faloutsos
Maria Ester
Gary Cooper
Joan Catlett
Paul Bradley
Paul Kelly
John Anderson
data-mining
Greg Hulten
Joseph Han
Joseph Han
Gary Cooper
content-based
Tom Huang
Chris Faloutsos
John Anderson
concepts
Chris Brunk
Dave Angluin
Dan Aha
Dan Aha
clustering
Soha Guha
Maria Ester
Paul Bradley
Yi Li
classification-rules
Wayne Bunt
Wayne Bunt
causal-relationships
Gary Cooper
buildings
Yi Li
blobs
Chuck Carson
weighting
Dan Aha
triangle-inequality
Andy Berman
Andy Berman
John Barros
time-related
Joseph Han
temporal
Wesley Chu
spatial
Maria Ester
Wesley Chu
similarity
Andy Berman
John Barros
Ricardo Baeza-Yates
search
James Bach
relational
Chris Brunk
Joseph Han
region-based
Chuck Carson
recognition
Mauro Costa
Yi Li
query-trees
Ricardo Baeza-Yates
query-by-example
Paul Kelly
queries
Dave Angluin
pruning
Andy Berman
pose
Mauro Costa
neural-networks
Wayne Bunt
Yosama Mustafa
multimedia
Chris Faloutsos
medical
Wesley Chu
Paul Kelly
John Anderson
matching
Mauro Costa
Ricardo Baeza-Yates
lines
Yi Li
learning
Jaime Carbonell
Wayne Bunt
Wayne Bunt
Chris Brunk
Tom Huang
Dave Angluin
Dan Aha
Dan Aha
Dan Aha
Yosama Mustafa
Joan Catlett
knowledge
Joseph Han
Wesley Chu
instance-based
Dan Aha
instance-based
Dan Aha
information-retrieval
Jaime Carbonell
indexing
Mauro Costa
image-stack
Alfonso Cardenas
image-retrieval
Tom Huang
Wesley Chu
Alfonso Cardenas
Chuck Carson
Andy Berman
Andy Berman
John Barros
James Bach
Paul Kelly
John Anderson
image-management
James Bach
image-display
Alfonso Cardenas
distance-measures
Andy Berman
database
Greg Hulten
Joseph Han
Joseph Han
Soha Guha
Chris Faloutsos
Maria Ester
Gary Cooper
Joan Catlett
Paul Bradley
Paul Kelly
John Anderson
data-mining
Greg Hulten
Joseph Han
Joseph Han
Gary Cooper
content-based
Tom Huang
Chris Faloutsos
John Anderson
concepts
Chris Brunk
Dave Angluin
Dan Aha
Dan Aha
clustering
Soha Guha
Maria Ester
Paul Bradley
Yi Li
classification-rules
Wayne Bunt
Wayne Bunt
causal-relationships*
Gary Cooper
buildings*
Yi Li
blobs*
Chuck Carson
</details>
# 答案1
**得分**: 0
如果您在树中正确存储了关键词，那么您只需要对树执行反向中序遍历，以按排序顺序获取关键词。
因此，如果您想要打印整个树，您的print(Node t)方法应该类似于以下内容：
```java
private void print(Node t){
// 递归到树的最底部的左边。
print(t.right);
System.out.println(t.l);
// 在此处打印记录...
print(t.left);
}
英文:
If you are storing the keywords in the Tree correctly then all you need to do is preform a reverse inorder traversal on the tree to get the keywords in sorted order.
So your print(Node t) method should look something like this if you want to print the whole tree.
private void print(Node t){
// Recurse to the bottom left of tree.
print(t.right);
System.out.println(t.l);
// Print records here...
print(t.left);
}
答案2
得分: 0
您正在构建具有较大节点的树，这些节点位于左侧。
您的遍历算法从左到右打印，因此首先显示最大的值。
这是因为您的代码片段中的比较与通常的相反：
else if(nObj.keyword.compareTo(keyword) < 0) {
if(nObj.l == null) { // 如果为空，创建一个左节点
nObj.l = new Node(keyword);
如果当前节点是“B”，要插入的节点是“A”，那么它变成了：
if("B".compareTo("A") < 0) // False
如果您交换顺序，即：
keyword.compareTo(nObj.keyword) < 0
那么左侧将更小，您的树将按预期的顺序打印。
或者，您可以保持树的当前状态，但在打印树时先递归右侧。
英文:
You are building your tree with larger nodes on the left.
Your traversal algorithm prints left to right, so therefore it shows largest values first.
The order is because of your snippet here, where the comparison is reversed from what's normal:
else if(nObj.keyword.compareTo(keyword)<0) {
if(nObj.l==null) { // if it is empty, create a left node
nObj.l = new Node(keyword);
If the current node is "B" and the node to insert is "A", then it becomes:
if("B".compareTo("A") < 0) // False
If you swap the order, i.e.:
keyword.compareTo(nObj.keyword) < 0
Then the left will be smaller, and your tree will print in the expected order.
Alternatively, you can just keep the tree the way it is, but recurse the right-hand side first when printing the tree.
专注分享java语言的经验与见解，让所有开发者获益！
评论