Binary Tree смотреть онлайн

Join the course at https://spotle.ai/learn/data-structure for Java
https://spotle.ai/learn/data-structure-C%2B%2B for C++

Transcript:
Hi. Welcome to Spotle masterclass. We have recently learnt binary search. We have also learnt arrays, stack, queue earlier. All of these are linear data structures. But in real world, all structures, do not necessarily follow a linear model. Some follow a hierarchical structure, such as, the organizational structure in a company; a structure that may start at CEO, followed by directors at the next level, followed by senior management at the next level, until you come down to entry level employees in the company. Employees will have promotions. There will be terminations as well as new hires in the company. An organizational structure may go through re-structuring. And a linear data structure obviously is not the best fit to handle this hierarchical structure.

To handle such a hierarchical structure we implement binary tree. This is our topic of discussion today. A binary tree is a hierarchical data structure, in which data/ information/ object is stored at the nodes, and there can be at most two nodes under each node. The node, where the tree starts, is called the root node. The nodes which are under some node are called the children of that node. And the nodes which have child nodes are called the parent of those child nodes. The nodes, which do not have any child node, are called the leaf node. Each node in a binary tree can have at most two child nodes, the child nodes are called left child and right child.

Let us now create a binary tree from its root.

The root node is where the tree starts. For an empty tree root node is NULL. Let us create a root node and name it Spotle.ai. Let us now create two children for Spotle.ai. Let us take two companies that work under Spotle.ai, Spotle Learn and Spotle Hire. These two are the child nodes of the node Spotle.ai. And Spotle.ai is the parent node of these two nodes. Under Spotle Learn, you have two categories Learners and Instructors. Instructors can be broken down in two parts; Overseas and India Based. Under Spotle Hire you have Job Seekers and Employers. Now Job Seekers are of two types; Experienced and Freshers. So this is one binary tree structure we have just formed.

Can you guess how you can create this structure? Yes, use pointers. While defining a class make sure you have a variable holding the value of that node; along with it you will have two pointers pointing to the object of this class. It’s simple, like this.

Can you now write a program to create the tree structure that we just talked about? The binary tree starts at the root node Spotle.ai.

Now, I ask you to create few more nodes. Create Hiring Managers and Recruiters as two child nodes of the parent Employers. And Technology and Management as two types of instructors under Overseas Instructors as well as under India Based Instructors. Notice, here Employers, Overseas Instructors and India Based Instructors are no more leaf nodes in this structure. The new leaf nodes under them are these.

Can you modify your program to accommodate this change in the structure? Try this yourself. A code, however, will be shared on your dashboard.

Up to this, it was easy. Isn’t it? Now if we want to create two nodes Courses andInternship under Spotle Learn, and move the current state content of Spotle Learn under Courses node; can you modify your program to accommodate this change? I know you can. Try this yourself.

This is nothing but creating an object Courses of class node and point to the nodes Learners on its left pointer and Instructors on its right pointer. Assign left node pointer of Spotle Learn, which was earlier pointing to Learners now pointing to Courses. Create another object Internship of class node and point the right node pointer of Spotle Learn to this node instead of Instructors.

Now, at some point Spotle.ai decides that the company will keep two separate types Technology and Management only for the Overseas Instructors and for India Based Instructors this classification will be erased. You can’t just simply erase these two nodes, you have to modify your program to accommodate this change. How will you do this? Again I will ask you to try it yourself. A code will be shared on your dashboard later.

Now this is pretty much about creating, modifying or deleting a binary tree. The next is searching information in the binary tree. We will do this in our next video. Happy learning.

Join the course at https://spotle.ai/learn/data-structure for Java
https://spotle.ai/learn/data-structure-C%2B%2B for C++