Java:二叉树递归方法 [英] Java: binary tree recursion methods

问题描述

我对Java很陌生，我们的一项工作要求我创建一个包含具有int值的节点的二叉树.我的教授希望我们使用包含主要方法的一类.我应用了两种递归方法，一种是插入节点，另一种是显示现有节点.但是，每当我运行代码时，控制台仅显示我输入的最新节点.我使用的方法有问题吗?这是我到目前为止的内容:

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:

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

推荐答案

在遍历树以查找将新节点放置在何处时，您要将根节点设置为新节点.一个简单的选择是将当前根存储在一个临时变量中，并在插入节点后放回原处.

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

您也应该为traverseShow方法做类似的事情.

You should do something similar for your traverseShow method as well.

这篇关于Java:二叉树递归方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！