Table of Contents
1. Binary Tree structure concepts
Figure 1: A UML diagram of a Node for a LinkedList. It contains some data as well as a previous pointer and next pointer. 2. UML diagram of a Binary Tree's node. It also has a data member variable, and it has a node pointer to a left child and a node pointer to a right child.
Remember that a Linked List contains Nodes, and each Node contains the data, as well as a pointer to the next Node item (and maybe even the previous!) A tree-based structure is similar to a linked list type structure.
A Tree is also made up of Nodes, though a tree is hierarchical. The Node stores the data, as well as pointers to its children Nodes. For a Binary Tree, any given Node has a Left Child Node pointer and a Right Child Node pointer.
Figure 2: A small tree with "A" as the top (root) node, "B" to its left, and "C" to its right. The written code says: nodeA.data = "A"; nodeA.ptrLeft = nodeB; nodeA.ptrRight = nodeC;
Review 1. Which is which?
Linked List node:
Binary Tree node:
2. Complete binary trees
Figure 3: A tree drawing, there is a root node with 2 children. The left child has 2 children, and the right child has 1 child on the left side.
Complete binary tree: A complete binary tree is one where all nodes have 2 children, except possibly in the lowest level. Additionally:
- In the 2nd-to-lowest level, if a node has children, then all its siblings to its left must have 2 children each.
- If a node in the 2nd-to-lowest level has only one node, it must be a left child.
- This mean the tree fills from left-to-right.
Review 2. Is this binary tree complete?
Figure 4: A tree with "A" as its root node, with "B" as the left child of "A" and "C" as the right child of "A".
Review 3. Is this binary tree complete?
Figure 5: A tree with "A" as its root node, with "B" as the left child of "A" and "C" as the right child of "A". The "B" node has a right child "D".
3. Heaps
Figure 6: Another image of a Heap. The contents don't really matter, the important thing is that children are filled from left-to-right.
“In a heap data structure the node keys are always larger than their child nodes, but their children nodes are not in any particular order.” […]
“Three major characteristics make a heap data structure what it is: (a) A heap is a binary tree. (b) A heap is a complete data structure, meaning the rows of nodes are completely filled in from left to right without any gaps, […] (c) Every node in a heap is larger than or equal to its child nodes.”
From Data Structures and Algorithms for Game Developers, by Allen Sherrod, page 328-329
3.1. Identifying Heaps
Remember that the criteria for a heap is:
- (A) a heap is a binary tree,
- (B) a heap is complete, and
- (C) every node in a heap is larger than or equal to its child nodes (for a max-heap).
Review 4. ○ True or ○ False: A node's child can be larger than the node itself (for a max heap).
Review 5. Is this a heap?
Figure 7: A tree with 100 as its root. 100's left child is 50. 100's right child is 40. 50's left child is 15. 50's right child is 35. 40's left child is 27.
Review 6. Is this a heap?
Figure 8: A tree with 60 as its root. 60's left child is 20, and 60's right child is 70. 20's left child is 10, and 20's right child is 40. 40's left child is 30, and 40's right child is 50.
Review 7. Is this a heap?
Figure 9: A tree with 50 as the root. 50 has a left child of 100. 50 has a right child of 40.
3.2. Implementation of a Heap
Even though heaps are visualized as a binary tree, they are usually implemented with an array structure, with the root node (the node with the greatest value) being at index 0.
Figure 10: “Example of a complete binary max-heap with node keys being integers from 1 to 100 and how it would be stored in an array.” by Maxiantor; downloaded from https://en.wikipedia.org/wiki/Heap data structure#Implementation
With a heap implemented in this way, you can locate children and parents by modifying the index of a given node at position i (that is, item[i])
- Its left child, if it exists, is items[2 * i + 1]
- Its right child, if it exists, is items[2 * i + 2]
- Its parent, if it exists, is items[(i - 1) / 2]
Remember that only the root in items[0] does not have a parent.
From Data Abstraction & Problem Solving with C++: Walls and Mirrors 7th ed, by Carrano and Henry, page 489
Review 8. The root's index is _ , the root's left child is at index _ , the root's right child is at index _ .
Review 9. Given this heap:
Figure 11: A tree with 100 as its root. 100's left child is 80. 100's right child is 50.
What would the array look like?
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
| Value | _ | _ | _ | _ | _ | _ |