java - 如何按字母顺序（abc）而不是倒序（zyx）将我的输出打印关键字*？这是java中的二叉搜索树实现

Question

类 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);
    } 
}

} //这是我的输出：Wesley Chu* 基于知识的图像检索与空间和时间约束加权* Dan Aha 三角不等式* Andy Berman Andy Berman John Barros 时间相关 Joseph Han 时间 Wesley Chu 空间 Maria Ester Wesley Chu 相似性 Andy Berman John Barros Ricardo Baeza-Yates 搜索James Bach 关系 Chris Brunk Joseph Han 基于区域的 Chuck Carson 识别 Mauro Costa Yi Li 查询树 Ricardo Baeza-Yates 示例查询 Paul Kelly 查询 Dave Angluin 修剪 Andy Berman 姿势 Mauro Costa 神经网络 Wayne Bunt Yosama Mustafa 多媒体 Chris Faloutsos医疗卫斯理朱保罗凯利约翰安德森匹配毛罗科斯塔里卡多巴埃扎耶茨台词伊莉学习海梅卡博内尔韦恩邦特韦恩邦特克里斯布伦克汤姆黄戴夫安格鲁因丹阿哈丹阿哈丹阿哈尤萨马穆斯塔法琼卡特莱特知识约瑟夫汉卫斯理Chu 基于实例的 Dan Aha 基于实例的 Dan Aha 信息检索 Jaime Carbonell 索引 Mauro Costa 图像堆栈 Alfonso Cardenas 图像检索 Tom Huang Wesley Chu Alfonso Cardenas Chuck Carson Andy Berman Andy Berman John Barros James Bach Paul Kelly John Anderson 图像管理James Bach 图像显示 Alfonso Cardenas 距离测量 Andy Berman 数据库 Greg Hulten Joseph Han Joseph Han Soha Guha Chris Faloutsos Maria Ester Gary Cooper Joan Catlett Paul Bradley Paul Kelly John Anderson 数据挖掘 Greg Hulten Joseph Han Joseph Han Gary Cooper 基于内容的 Tom Huang Chris Faloutsos John Anderson 概念 Chris Brunk Dave Angluin Dan Aha Dan Aha 聚类 Soha Guha Maria Ester Paul Bradley Yi Li 分类规则 Wayne Bunt Wayne Bunt 因果关系 Gary Cooper 建筑物 Yi Li blobs Chuck Carson weighting Dan啊哈三角不等式 Andy Berman Andy Berman John Barros 时间相关 Joseph Han 时间 Wesley Chu 空间 Maria Ester Wesley Chu 相似性 Andy Berman John Barros Ricardo Baeza-Yates search James Bach 关系 Chris Brunk Joseph Han 基于区域的 Chuck Carson 识别 Mauro Costa Yi Li查询树 Ricardo Baeza-Yates 示例查询 Paul Kelly 查询 Dave Angluin 修剪 Andy Berman 姿势 Mauro Costa 神经网络 Wayne Bunt Yosama Mustafa 多媒体 Chris Faloutsos 医学 Wesley Chu Paul Kelly John Anderson 匹配 Mauro Costa Ricardo Baeza-Yates 线条 Yi Li学习 Jaime Carbonell Wayne Bunt Wayne Bunt Chris Brunk Tom Huang Dave Angluin Dan Aha Dan Aha Dan Aha Yosama Mustafa Joan Catlett 知识 Joseph Han Wesley Chu 基于实例 Dan Aha 基于实例 Dan Aha 信息检索 Jaime Carbonell 索引 MauroCosta 图像堆栈 Alfonso Cardenas 图像检索 Tom Huang Wesley Chu Alfonso Cardenas Chuck Carson Andy Berman Andy Berman John Barros James Bach Paul Kelly John Anderson 图像管理 James Bach 图像显示 Alfonso Cardenas 距离测量 Andy Berman 数据库 Greg Hulten Joseph Han Joseph Han Soha Guha Chris Faloutsos Maria Ester Gary Cooper Joan Catlett Paul Bradley Paul Kelly John Anderson 数据挖掘 Greg Hulten Joseph Han Joseph Han Gary Cooper 基于内容的 Tom Huang Chris Faloutsos John Anderson 概念 Chris Brunk Dave Angluin Dan Aha Dan Aha 聚类 Soha Guha Maria Ester Paul Bradley Yi Li 分类规则 Wayne Bunt Wayne Bunt 因果关系* Gary Cooper 建筑物* Yi Li blobs* Chuck CarsonBarros James Bach Paul Kelly John Anderson 图像管理 James Bach 图像显示 Alfonso Cardenas 距离测量 Andy Berman 数据库 Greg Hulten Joseph Han Joseph Han Soha Guha Chris Faloutsos Maria Ester Gary Cooper Joan Catlett Paul Bradley Paul Kelly John Anderson 数据挖掘 Greg Hulten Joseph Han Joseph Han Gary Cooper 基于内容的 Tom Huang Chris Faloutsos John Anderson 概念 Chris Brunk Dave Angluin Dan Aha Dan Aha 聚类 Soha Guha Maria Ester Paul Bradley Yi Li 分类规则 Wayne Bunt Wayne Bunt 因果关系* Gary Cooper 建筑物* Yi Li斑点*查克·卡森Barros James Bach Paul Kelly John Anderson 图像管理 James Bach 图像显示 Alfonso Cardenas 距离测量 Andy Berman 数据库 Greg Hulten Joseph Han Joseph Han Soha Guha Chris Faloutsos Maria Ester Gary Cooper Joan Catlett Paul Bradley Paul Kelly John Anderson 数据挖掘 Greg Hulten Joseph Han Joseph Han Gary Cooper 基于内容的 Tom Huang Chris Faloutsos John Anderson 概念 Chris Brunk Dave Angluin Dan Aha Dan Aha 聚类 Soha Guha Maria Ester Paul Bradley Yi Li 分类规则 Wayne Bunt Wayne Bunt 因果关系* Gary Cooper 建筑物* Yi Li斑点*查克·卡森Kelly John Anderson 数据挖掘 Greg Hulten Joseph Han Joseph Han Gary Cooper 基于内容的 Tom Huang Chris Faloutsos John Anderson 概念 Chris Brunk Dave Angluin Dan Aha Dan Aha 聚类 Soha Guha Maria Ester Paul Bradley Yi Li 分类规则 Wayne Bunt Wayne Bunt 因果关系关系* Gary Cooper 建筑物* Yi Li blobs* Chuck CarsonKelly John Anderson 数据挖掘 Greg Hulten Joseph Han Joseph Han Gary Cooper 基于内容的 Tom Huang Chris Faloutsos John Anderson 概念 Chris Brunk Dave Angluin Dan Aha Dan Aha 聚类 Soha Guha Maria Ester Paul Bradley Yi Li 分类规则 Wayne Bunt Wayne Bunt 因果关系关系* Gary Cooper 建筑物* Yi Li blobs* Chuck Carson

标签： java

Answer 1

如果您正确地将关键字存储在树中，那么您需要做的就是在树上执行反向中序遍历以按排序顺序获取关键字。

因此，如果您想打印整个树，您的 print(Node t) 方法应该看起来像这样。

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);

}