Java：二叉树递归方法

Question

我对java很陌生，我们的一个任务需要我创建一个包含int值的节点的二叉树。我的教授希望我们使用一个包含主要方法的类。我应用了两种递归方法，一种是插入节点，另一种是显示现有节点。然而，每当我运行我的代码时，控制台只显示我输入的最新节点。我使用的方法有什么问题吗？这是我到目前为止：

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."); 
     } 
    } 
} 
} 

Answer 1

当您遍历树来查找放置新节点的位置时，您正在将根设置为新节点。一个简单的选择是将当前根存储在临时变量中，并在插入节点后将其放回。

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; 
} 

你应该为你的traverseShow方法做类似的事情。