Unlike all of the data structures I've discussed previously, a binary tree is not a linear data structure, and is instead a hierarchical data structure. My go to real world example of a hierarchical structure is a family tree.
Elements below nodes are called children, and elements above nodes are called parents. Like other structures, the beginning node of a tree is called the root. A binary tree has the restriction that each node may only have at most 2 children.
As with most of our other data structures, we first need to implement a node class. We can then use node objects that we create as we fill our tree. Each node needs to have some kind of data, and a pointer to the left and right.
Implementing the tree itself is simple. A tree needs a root, but all information about the root's children is stored in the nodes.
Unlike other structures we've looked at, a binary tree can be constructed in a plethora of ways depending on how you want the tree to be structured. For this example we'll be implementing a binary search tree, meaning that the left child only contains data that is of lesser value than the parent's data and the right node contains data that is of greater value than the parent's data.
First we check if there is a root, and set it if there is not. Otherwise, we add our node to the tree using our helper method. This second part needs to be a helper method because we are going to use recursion to call it repeatedly.
In this method we check if the data is greater than or less than the value of the node we are looking at, then add it to the node if there is an opening, otherwise we run the method again until we find an available spot for the node.
There are many other methods we could add to work with a binary search tree, and even more when working with other forms of binary trees.
Trees are much more advanced than the linear data structures we've discussed in the past, and to be honest I'm mastering them myself. So in my next post I'll dive in to various ways we can navigate trees. Until then, think about other ways we could go about creating a tree.
The code from this post can be found here.
Top comments (1)
Thank you!