I'm learning about trees and heaps, and for an assignment I created a max heap that I populated with a list of integers.

I can add the numbers just fine, but I don't understand exactly where these numbers are going and how to access them when I do an in-order traversal. I have a linked List and a queue set up, but the numbers I added don't seem to be in either one of them.

Below is the method my teacher gave me to add elements, but when I look at it I don't understand where the added data is going. Where exactly are added elements stored and how would I access them once they've been added?

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class PriorityQueue 
{    
    LinkedList<Node> myList = new LinkedList<>(); 
    Queue<Node> nodes = new LinkedList<>();
    Node num;
    Node root;
    Node head;
    
    private Node addRecursive(Node current, int val)
    {
        //base case 
        if(current == null)
        {
            return new Node(val);       
        }
        if(val > current.value) 
        {
            current.left = addRecursive(current.left, val);
        }
        else if(val < current.value)
        {
            current.right = addRecursive(current.right, val);
        }
        else 
        {
            return current;
        }
        return current;
    }
    
    public void add(int val)
    {
        root = addRecursive(root,val);
    }

CodePudding user response：

I created max heap

It might be that other code does that, but the code you have shared creates a binary search tree.

Where exactly are added elements stored

Each value is stored in a Node instance. Let's see what happens when you execute the following code:

PriorityQueue p = new PriorityQueue();

The instance p has several member variables, but only root is relevant for the methods add and addRecursive. It starts out with the default value null. We can picture the structure as follows:

  p
  ↓
┌────────────┐   
│ root: null │
└────────────┘

Then let's add a value:

p.add(5);

As root is null, the value of the current parameter variable is null too. We get in the "base case", and addRecursive returns a new node with the given value. The add method assigns this returned new node to root, so we end up with one node instance that can be accessed via root. We can picture it like so:

  p
  ↓
┌────────────┐    ┌─────────────┐
│ root: ─────────►│ value: 5    │
└────────────┘    │ left: null  │
                  │ right: null │
                  └─────────────┘

Let's add a second value:

p.add(2);

Now root is not null, and the value of the current parameter variable is same reference. We find that val < current.val (which evaluates to 2 < 5) is a true expression, so we get into the first else if block. There we make a recursive call with:

current.right = addRecursive(current.right, val);

As current.right is null, this recursive call will execute the base case, and when it returns, a new node with value 2 is here assigned to current.right. Execution continues to return current (which is the root reference) and add gets this root reference back and assigns it to root. This last assignment doesn't change root, as it already had that reference. The essential assignment here, was the one to current.right.

We can picture the result like so:

  p
  ↓
┌────────────┐    ┌─────────────┐
│ root: ─────────►│ value: 5    │
└────────────┘    │ left: null  │
                  │ right: ───────┐ 
                  └─────────────┘ │
                                  ▼
                               ┌─────────────┐
                               │ value: 2    │
                               │ left: null  │
                               │ right: null │
                               └─────────────┘ 

I would encourage you, to repeat this step-by-step process on a piece of paper for adding more values.

how would I access them once they've been added

In the above example with two node instances, you can access the values with these expressions:

p.root.value;  // 5
p.root.right.value; // 2

how to access them when I do an in-order traversal

An in-order traversal could collect the nodes in a list, but I would not make that list a member variable of your class. A method could make the traversal and return the list to the caller. Whether the caller wants to assign it to a member variable or not is their business...

Here are methods for an in-order traversal:

    // Helper function
    private void inOrderRecursive(Node current, LinkedList<Node> list) {
        if (current == null) {
            return;
        }
        inOrderRecursive(current.left, list);
        list.add(current);
        inOrderRecursive(current.right, list);
    }
    
    public LinkedList<Node> inOrder() {
        LinkedList<Node> list = new LinkedList<>();
        inOrderRecursive(root, list);
        return list;
    }

You can call it as follows:

        for (Node node : p.inOrder()) {
            System.out.print(node.value   " ");
        }

For the little binary search tree we created, the above would output:

5 2