在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并没有真正帮助理解你的代码。