l oadOverToLinkedTree( ). This methods is NOT recursive! Return type BinaryNode
ID: 3740615 • Letter: L
Question
loadOverToLinkedTree( ). This methods is NOT recursive! Return type BinaryNode parameters: E [ ] data, ArrayList<BinaryNode<E>> nodes. (Java)
Given the array representation of a binary tree the method creates a linked binary tree to represent the same data. The array is a parameter for the method. The other parameter nodes is for helping to link correctly the tree. The ArrayList nodes is like a parallel array for data and it is intended to maintain temporary references of the instantiated tree nodes until their links have been established
? The method loads over the data from the array to the nodes of the linked tree and returns the root (return type BinaryNode) 3
? The client must supply (precondition) an instantiated ArrayList of BinaryNode elements (for the client E is going to be a concrete type).
Pseudo-code:
? instantiate root with the data[0] and add root to the nodes list
? run a for loop over the data array from index 1.
? for k as current index instantiate a BinaryNode current with the data[k].
? Go back to the parent index p from k, use the parent child rule of array representation.
? if k is the left child from p, assign current to the left link of the parent node
? else assign current to the right link of the parent node
? add current to the ArrayList at index k
? end for loop
? return root
Explanation / Answer
public class BinaryNode { int key; BinaryNode left; BinaryNode right; public BinaryNode( int key){ this.key = key; // this.left = left; //this.right = right; } } public class BinaryTree { BinaryNode root; public void insert(int key){ BinaryNode newNode = new BinaryNode(key); if(root == null){ root = newNode; }else{ BinaryNode focusNode = root; BinaryNode parent; while(true){ parent = focusNode; if(keyRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.