Создание BST из списка ввода пользователя в Java

Question

Я пытаюсь создать двоичное дерево поиска из списка, который предлагает пользователям вводить данные.Я могу заставить код работать, когда я вручную присваиваю каждому узлу его значение.Но когда я зацикливаюсь на вводе каждого значения, при выводе списка он пуст и читает [0,0,0,0,0,0].Когда мне предлагается ввести количество узлов, например, 7, мне нужно 7 раз ввести значение, после чего оно заканчивается.Но когда он выводит список, список пуст.Любые указатели на то, что я делаю не так в драйвере?Затем я возьму этот список и преобразую его в BST.

enter code here
import java.util.Scanner;
import java.io.*; 
import java.util.*;

public class LinkedList { 

/* head node of link list */
static LNode head; 

/* Link list Node */
class LNode  
{ 
    int data; 
    LNode next, prev; 

    LNode(int d)  
    { 
        data = d; 
        next = prev = null; 
    } 
} 

/* A Binary Tree Node */
class TNode  
{ 
    int data; 
    TNode left, right; 

    TNode(int d)  
    { 
        data = d; 
        left = right = null; 
    } 
} 

/* This function counts the number of nodes in Linked List 
   and then calls sortedListToBSTRecur() to construct BST */
TNode sortedListToBST()  
{ 
    /*Count the number of nodes in Linked List */
    int n = countNodes(head); 

    /* Construct BST */
    return sortedListToBSTRecur(n); 
} 

/* The main function that constructs balanced BST and 
   returns root of it. 
   n  --> No. of nodes in the Doubly Linked List */
TNode sortedListToBSTRecur(int n)  
{ 
    /* Base Case */
    if (n <= 0)  
        return null; 

    /* Recursively construct the left subtree */
    TNode left = sortedListToBSTRecur(n / 2); 

    /* head_ref now refers to middle node,  
       make middle node as root of BST*/
    TNode root = new TNode(head.data); 

    // Set pointer to left subtree 
    root.left = left; 

    /* Change head pointer of Linked List for parent  
       recursive calls */
    head = head.next; 

    /* Recursively construct the right subtree and link it  
       with root. The number of nodes in right subtree  is  
       total nodes - nodes in left subtree - 1 (for root) */
    root.right = sortedListToBSTRecur(n - n / 2 - 1); 

    return root; 
} 

/* UTILITY FUNCTIONS */
/* A utility function that returns count of nodes in a  
   given Linked List */
int countNodes(LNode head)  
{ 
    int count = 0; 
    LNode temp = head; 
    while (temp != null) 
    { 
        temp = temp.next; 
        count++; 
    } 
    return count; 
} 

/* Function to insert a node at the beginging of  
   the Doubly Linked List */
void push(int new_data)  
{ 
    /* allocate node */
    LNode new_node = new LNode(new_data); 

    /* since we are adding at the begining, 
       prev is always NULL */
    new_node.prev = null; 

    /* link the old list off the new node */
    new_node.next = head; 

    /* change prev of head node to new node */
    if (head != null) 
        head.prev = new_node; 

    /* move the head to point to the new node */
    head = new_node; 
} 

/* Function to print nodes in a given linked list */
void printList(LNode node)  
{ 
    while (node != null)  
    { 
        System.out.print(node.data + " "); 
        node = node.next; 
    } 
} 

/* A utility function to print preorder traversal of BST */
void preOrder(TNode node)  
{ 
    if (node == null) 
        return; 
    System.out.print(node.data + " "); 
    preOrder(node.left); 
    preOrder(node.right); 
} 
//   public static  Object root(TNode root) {
//      return root;
//  }

/* Drier program to test above functions */
public static void main(String[] args) { 
      LinkedList lList = new LinkedList();
        Scanner scanner = new Scanner(System.in);
        // define how many nodes will be in the list
        System.out.println("How many nodes would you like to Enter:");
        int n = scanner.nextInt();
        int input[] = new int[n];
        // enter each node
        System.out.println("Enter the nodes:");
        for (int i = 0; i < n; i++)
        {
            // store values into the list
            int currInput = scanner.nextInt();
            lList.add(currInput);
            input[i] = currInput;
        }
        System.out.println("Given Linked List: ");
        System.out.println(Arrays.toString(input));

//      System.out.println("Given Linked List: ");
//      System.out.println(Arrays.toString(llists));
    //System.out.println(llists.length);
    /* Let us create a sorted linked list to test the functions 
       Created linked list will be 7->6->5->4->3->2->1 */
   // llist.push(7); 
   // llist.push(6); 
   // llist.push(5); 
   // llist.push(4); 
   // llist.push(3); 
   // llist.push(2); 
   // llist.push(1); 

    System.out.println("Given Linked List "); 

    //llist.printList(head); 

    /* Convert List to BST */
    TNode root = lList.sortedListToBST(); 
    System.out.println(""); 
    System.out.println("Pre-Order Traversal of constructed BST "); 
    lList.preOrder(root); 
    System.out.println("The root of the tree is: ");
    System.out.println(root.data);
}

private static int add(int nextInt) {
// TODO Auto-generated method stub
return 0;
} 

}

Answer 1

Я думаю, ваше соглашение об именах затрудняет понимание кода.Попробуйте изменить код добавления пользовательского ввода в массив с

llists[i] = add(scanner.nextInt());

на

llists[i] = scanner.nextInt();

Я думаю, что вы смешали 2 структуры данных, используя почти идентичные имена, то есть длямассив и связанный список.Использование add можно найти здесь: https://www.geeksforgeeks.org/java-util-linkedlist-add-method-in-java/

Попробуйте использовать это,

        // create a sorted linked list from user input
    LinkedList lList = new LinkedList();
    Scanner scanner = new Scanner(System.in);
    // define how many nodes will be in the list
    System.out.println("How many nodes would you like to Enter:");
    int n = scanner.nextInt();
    int input[] = new int[n];
    // enter each node
    System.out.println("Enter the nodes:");
    for (int i = 0; i < n; i++)
    {
        // store values into the list
        int currInput = scanner.nextInt();
        lList.add(currInput);
        input[i] = currInput;
    }
    System.out.println("Given Linked List: ");
    System.out.println(Arrays.toString(input));

Также, вы не против добавить свое определение TreeNode.

PS, таммогут быть и другие интерпретации для кода Даниэля Роджера, например, функция add (), но я попытался разбить ее на простейшее, что мог.