Java:二叉树递归方法

Question

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

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 方法执行类似的操作。