二分查找樹

Question

class Student 
{ 
    String name; 
    int roll; 
    int age; 
    public Student(String n,int r,int a) { 
     name=n; 
     roll=r; 
     age=a; 
    } 
    public String retname() { 
     return name; 
    } 
    public int retroll() { 
     return roll; 
    } 
    public int retage() { 
     return age; 
    } 
    public void displaystudent() { 
     System.out.print("Name : "+name+" Roll : "+roll+" Age : "+age+"\n"); 
    } 
} 

class Node 
{ 
    Student s; 
    Node lchild; 
    Node rchild; 
    public Node(String n,int r ,int a) { 
     s=new Student(n,r,a); 
    } 
    public void displayNode() { 
     s.displaystudent(); 
    } 
} 
class Tree 
{ 
    public Node root; 
    public void insert(String n,int r,int a) { 
     Node newNode=new Node(n,r,a); 
     if(root==null) 
      root=newNode; 
     else { 
      Node current=root; 
      Node parent; 
      while(true) { 
       parent=current; 
       if(n.compareTo(current.s.retname())<0) { 
        current=current.lchild; 
        if(current==null) 
         parent.lchild=newNode; 
        return; 
       } else { 
        current=current.rchild; 
        if(current==null) 
         parent.rchild=newNode; 
        return; 
       } 
      } 
     } 
    } 
    public void order() { 
     inorder(root); 
     preorder(root); 
     postorder(root); 
    } 
    public void inorder(Node localroot) { 
     if(localroot!=null) { 
      inorder(localroot.lchild); 
      localroot.displayNode(); 
      inorder(localroot.rchild); 
     } 
    } 
    public void preorder(Node localroot) { 

     if(localroot!=null) { 
      preorder(localroot.lchild); 
      preorder(localroot.rchild); 
      localroot.displayNode(); 
     } 
    } 
    public void postorder(Node localroot) { 
     if(localroot!=null) { 
      localroot.displayNode(); 
      postorder(localroot.lchild); 
      postorder(localroot.rchild); 
     } 
    } 
} 
class e 
{ 
    public static void main(String [] args) { //throws IOException 

     Tree t=new Tree(); 
     t.insert("E",1,23); 
     t.insert("D",2,2); 
     t.insert("C",3,4); 
     t.insert("B",4,89); 

     t.insert("A",5,45); 

     t.order(); 
    } 
} 

上面的代碼沒有顯示它應該的所有輸出。另外，爲什麼前序和中序給出了相同的結果？ 另外，如何在不從根開始的子樹中進行遍歷？ 有什麼辦法可以避免遞歸嗎？

這是當前不正確的輸出。它應該打印我插入的所有元素，也以特定順序打印。

Name : D Roll : 2 Age : 2 
Name : E Roll : 1 Age : 23 
Name : D Roll : 2 Age : 2 
Name : E Roll : 1 Age : 23 
Name : E Roll : 1 Age : 23 
Name : D Roll : 2 Age : 2 

Answer 1

我注意到的最明顯的第一個問題是在您的insert方法中。在這種方法中，在檢查while循環的下一次迭代之前，總是返回（如果根有子子項，則不會插入任何內容）。要修正這個錯誤，只是改變你的while循環是這樣的：

while(true) 
    { 
     parent=current; //assign parent to root 
     if(n.compareTo(current.s.retname())<0) 
     { 
      current=current.lchild; 
      if(current==null) {//added brackets so the return only happened when this was true 
       parent.lchild=newNode; 
       return; 
      } 
     } 
     else 
     { 
     current=current.rchild; 
     if(current==null){ //added brackets so the return only happened when this was true 
      parent.rchild=newNode; 
      return; 
      } 
     } 
    }  

做了這些改變後，你的其他問題可以在有自己的回答。做出這些改變，看看它是否能解決你的問題，如果沒有評論讓我知道，我會再看看。

編輯之一：

我認爲你的預購是錯誤的。我相信你應該在之前分別打印節點遞歸遍歷左邊和右邊的孩子。它應該看起來像這樣：

public void preorder(Node localroot) { 

    if(localroot!=null) { 
     localroot.displayNode(); //here! 
     preorder(localroot.lchild); 
     preorder(localroot.rchild); 
     //localroot.displayNode(); not here! 
    } 
}