Objectives
Create a binary tree and compare values of 2 binary trees.
Supports Leaning Outcome 3
3. Implement data structures and algorithms in computer code.
Lectures
You should have gone through all the tree-based structures prior to this assignment. We are now going to move into more independent research and implementation. One of the objectives is that all students can research, implement, and use a data structure.
This assignment will use a simple implementation of a binary tree with each node having an implementation of left, and right (which are nodes).
The other algorithm that you need to implement will be to compare the trees.
function CompareTrees(tree1, tree2) {
// Spans the tree to see if each tree contains the same
// values and structure
// returns unequal, equivalent, or equal
}
Assignment
Create the following 2 trees.
|
Tree 1
|
Tree 2
|
You can call these trees by any name. You will need to implement a BinaryTree Object. This is very similar to making a List where each node points to a Left and a Right Node. A little research should help you get this pretty easily at this point.
The next step is to compare the lists. There are 3 possible states of the Trees;
1. They are unequal – they do not contain the same structure or elements
2. They are equivalent – they contain the same elements, but not the same structure.
3. They are equal – they contain the same structure and elements.
The example trees are equivalent (they both contain 1,2,4,8,16 with a different structure – your function(s) should compare the 2 trees and arrive at this conclusion.