在Java中實現二叉搜索樹

Question

這是我爲二叉搜索樹編寫的代碼。不幸的是，當我運行它時，它不會提供所需的輸出。有人能告訴我我做錯了什麼嗎？

import java.util.ArrayList; 


public class BinaryOrderedTree { 
    BinaryOrderedTree left; 
    BinaryOrderedTree right; 
    static BinaryOrderedTree top; 
    int key; 
    static ArrayList<BinaryOrderedTree> values=new ArrayList<BinaryOrderedTree>(); 



    public int getKey(){ 
     return key; 
    } 


    public void setTop(BinaryOrderedTree top1){ 
     top=top1; 
    } 

    public BinaryOrderedTree getLeft(){ 
     return this.left; 
    } 

    public BinaryOrderedTree getRight(){ 
     return this.right; 
    } 

    public BinaryOrderedTree(int key){ 
     this.key=key; 
    } 

    public static BinaryOrderedTree addNode(BinaryOrderedTree node,BinaryOrderedTree top){ 
     if (node.getKey()<top.getKey()){ 
      if(top.left==null){ 
       System.out.println(node.getKey()); 
       System.out.println("left"); 
      top.left=node; 
      } 
      else{ 
       addNode(node,top.left); 
      } 
     } 
     if(node.getKey()>top.getKey()){ 
      if(top.right==null){ 
       System.out.println(node.getKey()); 
       System.out.println("right"); 
       top.right=node; 
      } 
      else{ 
       addNode(node,top.right); 
      } 
     } 
     return node; 
    } 

    public static BinaryOrderedTree searchNode(BinaryOrderedTree search, 
      BinaryOrderedTree top){ 
     if(search.getKey()==top.getKey()){ 
      return top; 
     } 
     else if(search.getKey()<top.getKey()){ 
      return searchNode(search,top.left); 
     } 
     else if(search.getKey()>top.getKey()){ 
      return searchNode(search,top.right); 
     } 
     return null; 
    } 

    public static BinaryOrderedTree traverse(BinaryOrderedTree top){ 
     values.add(top); 
     System.out.println(top.getKey()); 
     if(top.left !=null) 
     traverse(top.left); 
     else if (top.right!=null) 
     traverse(top.right); 
     values.add(top.left); 
     values.add(top.right); 
     return top; 
    } 

    public static void main(String[] args){ 
     BinaryOrderedTree top=new BinaryOrderedTree(7); 
     BinaryOrderedTree firstNode=new BinaryOrderedTree(6); 

     BinaryOrderedTree.addNode(firstNode,top); 
     BinaryOrderedTree secondNode=new BinaryOrderedTree(4); 
     BinaryOrderedTree.addNode(secondNode, top); 
     BinaryOrderedTree thirdNode=new BinaryOrderedTree(8); 
     BinaryOrderedTree.addNode(thirdNode, top); 
     BinaryOrderedTree fourthNode=new BinaryOrderedTree(3); 
     BinaryOrderedTree.addNode(fourthNode, top); 
     BinaryOrderedTree.traverse(top); 
//  System.out.println(BinaryOrderedTree.values); 
    } 
} 

This is the output I get 

    6 
left 
4 
left 
8 
right 
3 
left 
traversing pre-order 
7 
6 
4 
3 

我只能假設節點被正確添加。但是，它無法顯示頂部節點右側的節點，只能遍歷左側部分。有人能指出這個缺陷。

Answer 1

在你的右邊遍歷刪除else：

if(top.left !=null) 
    traverse(top.left); 
if (top.right!=null) 
    traverse(top.right); 

---

BTW你values可能會充滿詭異的爲好。 values.add(top)就足夠了。刪除那些values.add(top.left)和values.add(top.right)。

---

BTW（一個）variable shadowing並沒有真正幫助理解你的代碼。