Java：二叉树递归方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17777011/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: binary tree recursion methods
提问by user2604960
I'm quite new to java and one of our assignments requires me to create a binary tree containing nodes with int values. My professor wants us to use one class containing the main method. I applied two recursive methods, one to insert a node and one to display existing nodes. Whenever I run my code however, the console only displays the most recent node that I entered. Is there something wrong with the methods I used? This is what I have so far:
我对 java 很陌生，我们的一项任务要求我创建一个二叉树，其中包含具有 int 值的节点。我的教授希望我们使用一个包含 main 方法的类。我应用了两种递归方法，一种用于插入节点，另一种用于显示现有节点。然而，每当我运行我的代码时，控制台只显示我输入的最新节点。我使用的方法有问题吗？这是我到目前为止：
import java.util.Scanner;
public class node {
private int value;
static node root;
public node leftLink;
public node rightLink;
public node(int v)
{
this.value = v;
}
public int getValue()
{
return value;
}
static void traverseShow()
{
if(root.leftLink != null){
root = root.leftLink;
traverseShow();
}
System.out.println(root.getValue());
if(root.rightLink != null)
{
root = root.rightLink;
traverseShow();
}
return;
}
static void addNode(node n)
{
if(root==null)
{
root = n;
}
else
{
if(root.getValue()>n.getValue())
{
root = root.leftLink;
addNode(n);
}
if(root.getValue()<n.getValue())
{
root = root.rightLink;
addNode(n);
}
}
return;
}
public static void main(String[] args)
{
int val = 0;
Scanner sc = new Scanner(System.in);
boolean loop = true;
String command = "";
while(loop==true)
{
System.out.println("Please enter a command:");
System.out.println("A = insert a new value");
System.out.println("B = display all values");
System.out.println("C = exit program");
command = sc.next();
if(command.equalsIgnoreCase("a"))
{
System.out.println("Enter value: ");
val = sc.nextInt();
node newNode = new node(val);
addNode(newNode);
}
else if(command.equalsIgnoreCase("b"))
{
traverseShow();
}
else if(command.equalsIgnoreCase("c"))
{
sc.close();
System.exit(0);
}
else
{
System.out.println("Invalid command! Please try again.");
}
}
}
}
回答by jonhopkins
You're setting the root to the new node when you're traversing the tree to find where to put the new node. One simple option is to store the current root in a temporary variable and put it back after you insert the node.
当您遍历树以查找放置新节点的位置时，您将根设置为新节点。一个简单的选择是将当前根存储在一个临时变量中，并在插入节点后将其放回原处。
static void addNode(node n)
{
if(root==null)
{
root = n;
}
else
{
node tmp = root; // save the current root
if(root.getValue()>n.getValue())
{
root = root.leftLink;
addNode(n);
}
else if(root.getValue()<n.getValue())
{
root = root.rightLink;
addNode(n);
}
root = tmp; // put the root back to its original value
}
return;
}
You should do something similar for your traverseShow method as well.
您也应该为您的 traverseShow 方法做类似的事情。
