Binary Trees and Heap Implementation in Java
Explore the concepts of binary trees, heap implementation, and traversal techniques in Java through engaging peer instruction materials by Cynthia Lee. Learn about heap uniqueness, in-place heapsort, and generic binary trees. Test your knowledge with reading quizzes and analyze heap outcomes based on insert order. Interactive content makes learning data structures fun and informative.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Creative Commons License CS2 in Java Peer Instruction Materials by Cynthia Lee is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CSE 12 Basic Data Structures Cynthia Bailey Lee Some slides and figures adapted from Paul Kube s CSE 12
2 Today s Topics 1. Heap implementation issues Heap uniqueness Heapsort in place HW suggestions 2. Back to generic binary trees In-order traversal Pre-order traversal Post-order traversal Level-order traversal (also called breadth-first )
Reading quiz! 1. A node in a binary tree may have ___ children A. 0 B. 1 C. 2 D. 3 E. Other/none of the above/more than one of the above
Reading quiz! 2. A preorder traversal visits the current node, performs a preorder traversal of its ___ subtree and then performs a preorder traversal of the its ___ subtree. A. right, right B. left, right C. left, left D. right, left
Reading quiz! 3. A full binary tree is a tree in which every node other than the leaves has ____ children. A. 0 B. 1 C. 2 D. 3 E. Other/none of the above/more than one of the above
TRUE OR FALSE There is only one configuration of a valid min-heap containing the elements {34, 22, 3, 9, 18} A. TRUE B. FALSE
Heap outcomes by insert order Create a MIN-heap by inserting the elements, one by one, in the order given below for the first letter of your last name: A-F: {3, 9, 18, 22, 34} G-L: {3, 33, 18, 9, 34} M-R: {9, 22, 18, 3, 34} S-Z: {18, 22, 3, 9, 34}
Heap outcomes by insert order Create a MIN-heap by inserting the elements, one by one, in the order given below for the first letter of your last name: A-F: {18, 9, 34, 3, 22} G-L: {3, 18, 22, 9, 34} M-R: {22, 9, 34, 3, 18} S-Z: {34, 3, 9, 18, 22}
How many distinct min-heaps are possible for the elements {3, 9, 18, 22, 34} ? A. 1 B. 2-4 C. 5-8 D. 5! (5 factorial) E. Other/none/more
Heapsort is super easy 1. Insert unsorted elements one at a time into a heap until all are added 2. Remove them from the heap one at a time. We will always be removing the next biggest[smallest] item from the max-heap[min-heap], so the items come out in sorted order! THAT S IT!
Example: using heapsort to print an array in sorted order (note: this is not the in- place version you need for HW) public static void printSorted(String[] unsortedlist) { Heap<String> heap = new Heap<String>(); for (int i=0; i<unsortedlist.length; i++) { heap.add(unsortedlist[i]); } while (!heap.isEmpty()) { System.out.println(heap.remove()); } }
Implementing heapsort Devil s in the details
We can do the entire heapsort in place in one array Unlike mergesort, we don t need a separate array for our workspace We can do it all in place in one array (the same array we were given as input)
Build heap by inserting elements one at a time:
Sort array by removing elements one at a time:
Build heap by inserting elements one at a time IN PLACE:
Sort array by removing elements one at a time IN PLACE:
Important tip! The in-place approach will not work if your test to see if index i is past the end of the heap is to check if heaparray[i] is null. Things will be in the array that are NOT in the heap! You need to keep track of an int size (in addition to an int capacity) in order to check where the heap ends!
Binary trees Recall from last time, a binary tree is any tree where each node has 0, 1, or 2 children That s the only restriction Recall: heaps are a special case of binary trees, and they have two additional restrictions
Trees vs. Lists Lists have an obvious ordering 1st element is first, 2nd element is second, Trees don t More than one reasonable order
Pre-order traversal preorder(node) { if (node != null){ visit this node preorder(node.left) preorder(node.right) } } A. D B E A F C G B. A B D E C F G C. A B C D E F G D. D E B F G C A E. Other/none/more
Post-order traversal postorder(node) { if (node != null){ postorder(node.left) postorder(node.right) visit this node } } A. D B E A F C G B. A B D E C F G C. A B C D E F G D. D E B F G C A E. Other/none/more
In-order traversal inorder(node) { if (node != null){ inorder(node.left) visit this node inorder(node.right) } } A. D B E A F C G B. A B D E C F G C. A B C D E F G D. D E B F G C A E. Other/none/more
