用Java实现指针式BST

Question

现在，我清楚地理解Java引用是"按值传递"

以及

Ref r=null;
....
method m1(Ref r)
{
r=r2;
..
}
..//r remains null

但我刚刚用Java写了一个C指针风格的BST程序，使用了3 in、post、pre-order遍历和其他方法，现在有没有什么方法可以通过修改几行来调整它，我想不出。。。

请建议一些方法来获得这个工作

Java中是否有任何语言构造允许我们像对待C指针一样对待Java引用

Node.java

public class Node{

private int key;
private Node left;
private Node right;
Node(int key)
{
    this.key=key;
    left=null;
    right=null;//redundant as java by default sets to null
}
public int getKey()
{
    return key;
}
public void setKey(int value)
{
    key=value;
}

public Node getLeft()
{
    return left;
}
public  void setLeft(Node left)
{
    this.left=left;
}

public Node  getRight()
{
    return right;
}
public  void setRight(Node right)
{
    this.right=right;
}


}//class Node ends

BST.java

import java.io.*;
import java.util.*;
public class BST {
    private Node root;
    BST()
    {
        root=null;
    }
    public void insert(int value,Node n)
    {
        if(n==null)//found place to enter ,so enter the value there
        {   System.out.println("nInserting "+value);
            n=new Node(value);
            //n.setKey(value);
        }
        else//need to traverse accordingy
        {
            if(value<n.getKey())//go left
            {
                insert(value,n.getLeft());
                System.out.println("Left of");
            }
            else if (value>n.getKey())//go right
            {
                insert(value,n.getRight());
            }
            else//its a duplicate
            {
                System.out.println("duplicate");
            }

        }
    }
    void preorder(Node n)
    {   System.out.println("Inside Preorder");
        if(n!=null)
        {   System.out.println("Traversing Inorder");
            System.out.println(" "+n.getKey());
            preorder(n.getLeft());
            preorder(n.getRight());
        }
    }
    void postorder(Node n)
    {
        if(n!=null)
        {
            postorder(n.getLeft());
            postorder(n.getRight());
            System.out.println(" "+n.getKey());
        }
    }

    void inorder(Node n)
    {
        if(n!=null)
        {
            inorder(n.getLeft());
            System.out.println(" "+n.getKey());
            inorder(n.getRight());
        }
    }
public Node getroot()
{
    return root;
}

public static void main(String[] args)
{
BST bst=new BST();
int ch=0;
Scanner sc=new Scanner(System.in);
while(true)
{
    System.out.println("Enter choice 1:Insert ,2:Pre Order,3:PostOrder,4:Inorder 0:Exit");
    ch=sc.nextInt();
    switch(ch)
    {
    case 1:
    System.out.println("nENter the number of elements");
    int n=sc.nextInt();
    int[] temp=new int[n];
    System.out.println("Enter elements to insert");
    for(int i=0;i<n;i++)
    {
        temp[i]=sc.nextInt();
    }

    for(int ele:temp)
    {
    bst.insert(ele,bst.getroot());
    }
    //done inserting all elements
    break;
    case 2:
    System.out.println("PreOrder traversal is n");
    bst.preorder(bst.getroot());
    break;
    case 3:
    System.out.println("PostOrder traversal is n");
    bst.postorder(bst.getroot());
    break;
    case 4:
    System.out.println("InOrder traversal is n");
    bst.inorder(bst.getroot());
    break;

    case 0:
    System.out.println("Exiting");
    System.exit(0);
    break;
    default:
    System.out.println("Enter valid choice");
    }//switch ends
}//loop ends
}// main ends
}//class BST ends

Answer 1

我不知道我是否理解正确，但问题似乎出在insert方法（int值，Node n）中，其中n变量在该方法中接收一个实例。

如果问题确实是您可以返回实例，而不是在方法内部分配变量，那么您可以使用返回的值，然后将传递的变量设置为参数。看起来像：

  public Node insert(int value,Node n){
    if(n==null){
        return new Node(value);
    }else{
        if(value<n.getKey()){
            Node newNode = insert(value,n.getLeft());
            if(n.getLeft()==null){
              n.setLeft(newNode);
            }
            return newNode;
        }else if (value>n.getKey()){
            Node newNode = insert(value,n.getRight());
            if(n.getRight()==null){
              n.setRight(newNode);
            }
            return newNode;
        }else{
            System.out.println("duplicate");
            return null;
        }
    }
}

我想说的另一点是，Java中已经有BST实现了，除非你使用这个模型来训练，否则只建议你使用已经存在的实现。