在 Java 中实现指针样式 BST?
Implement pointer style BST in Java?
现在,我清楚地了解到 Java 引用是 'Pass by value '
还有那个
Ref r=null;
....
method m1(Ref r)
{
r=r2;
..
}
..//r remains null
但我刚刚在 Java 中用 3 in、post、预序遍历和其他方法编写了一个 C 指针样式的 BST 程序,现在有什么方法可以通过以下方式对其进行调整修改几行,none我能想到...
请提出一些使此工作正常进行的方法
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
不知道我理解的对不对,问题好像出在insert方法(int value, Node n),n变量在这个方法中接收了一个实例。
如果问题确实是您可以 return 实例而不是在方法内部分配变量,那样的话,您可以使用 returned 值然后设置变量作为参数传递。看起来像:
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 实现,除非你使用这个模型来训练只建议你使用已经存在的实现。
现在,我清楚地了解到 Java 引用是 'Pass by value '
还有那个
Ref r=null;
....
method m1(Ref r)
{
r=r2;
..
}
..//r remains null
但我刚刚在 Java 中用 3 in、post、预序遍历和其他方法编写了一个 C 指针样式的 BST 程序,现在有什么方法可以通过以下方式对其进行调整修改几行,none我能想到...
请提出一些使此工作正常进行的方法
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
不知道我理解的对不对,问题好像出在insert方法(int value, Node n),n变量在这个方法中接收了一个实例。
如果问题确实是您可以 return 实例而不是在方法内部分配变量,那样的话,您可以使用 returned 值然后设置变量作为参数传递。看起来像:
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 实现,除非你使用这个模型来训练只建议你使用已经存在的实现。