Trees! Trees Everywhere! Much like the Ents in Lord of The Rings, this data structure was one of the first non-linear ones to appear and given its incredible versatility and adaptability, it has maintained relevance for decades.
In computer science, as you might recall, a tree is a very functional data structure that can be used to model a wide range of hierarchical information sets such as decision trees for game logic, file systems, and organizational charts. More advanced tree structures are used in image processing, geospatial indexing, searching (mapping), and form the backbone of most database and hashmap structures.
It is the simplicity of the tree that gives it superior performance with some specific trees capable of O(logn) time complexities across all four major procedures (search, sort, insert, and delete).
The core structure of the tree is the node, a simple data structure that we have used in with Linked Lists and Queues. We will build upon its versatility by putting together many nodes to grow our trees.
Throughout this lesson, we will create a Tree data structure that is capable of insertion, deletion, traversal, and printing. In the end, you will be given some challenges to increase the capability of our tree.
Let’s get started by taking a look at our Node class from the previous lessons and refactoring it into a TreeNode class to set the stage for our Tree.
Instructions
In Tree.swift, you will find the Node class that we built in previous lessons. The first thing to do is rename it to TreeNode. Our new TreeNode class will need to keep track of our children using an Array. We’ll also have no more need to track which Node is “next” since we can have multiple children, not just one Node.
In the TreeNode class:
- Rename the class from
NodetoTreeNode - Delete the instance variable,
next - Create a new instance variable,
childrenwith the type being an Array ofTreeNodes.
Don’t worry about the initializer error after you’ve completed these steps, we’ll deal with that in the next instruction.
Refactor the constructor to instantiate children to an empty Array. When you first create a TreeNode, you want it to have no children (a leaf node).
Now let’s test the changes we just made to check for errors. Outside of the TreeNode class, instantiate a new TreeNode variable with the name root with the String, “Planting my first seed!” as the data.
Print out the root’s data property using the print() function. We’ll create a better print method in the lessons to come; For now, we just want to see our tree growing!