Trees data structure
Trees data structure

Trees data structure

Hello friends today we are going to talk about another data structure and algorithm. Today we are going to discuss about trees data structure. So let’s see what are the topic outline.

Topic outline

  • What is a tree?
  • Types of tree data structure
  • Tree terminologies
    • Path
    • Root
    • Parent
    • Child
    • Leaf
    • Traversing
    • Levels
  • What is a binary search tree (BST)
  • Node class implementation for trees
  • operations in a tree
  • implementing the tree class
  • Deletion operations in binary search tree

What is a trees data structure?

Tree is a data structure. We have different types of trees. A tree made out of nodes and edges. Trees are known as an instance of graph. The tree data structure has a root. We can identify paths from root to down nodes.

Types of tree data structure

Earlier also I have told there are different types of trees. So they are binary and multiway.  Let’s look at what they are?

Binary tree – In these types of trees each node has only two children.

Multiway tree – In these types of trees nodes can have more than two children.

Tree terminologies

Path

The sequence of walking node to node along the edges.

Root

The top node in the tree is known as a root. There is one root per a tree.

Parent

The edges which nodes have running upwards.

Children

The edges which nodes have running downwards.

Leaf

A node in the tree which doesn’t have any children nodes is call as a leaf node.

Traversing

Visit all the nodes in the tree according to a special order.

Levels

How many generations a node is from the root. We assume that root is level zero.

What is a binary search tree?

Binary tree is also a one of type of tree types. Binary trees has two children nodes per a node. Those nodes are arrange as a special order. That is a node’s left child has a value less than the parent node. The right child contains a value greater than parent node.

Node class implementation for trees

 

 

</span></p>
<pre class="wp-block-syntaxhighlighter-code"><span style="font-family: arial, helvetica, sans-serif;"> class Node{
	int iData;
	double fData;
	Node leftChild;
	Node rightChild;
}</span></pre>
<p><span style="font-family: arial, helvetica, sans-serif;">

 

Operations in a tree

Finding

Inserting

Deleting

Traversing

Displaying

Implementing the tree class

class Tree{
private Node root;

public Node find(int key){

}

public void insert(int id,double dd){

}

public void delete(int id){

}

public void display(){

}
}

Creating TreeApp class

class TreeApp{
public static void main(String args[]){
tree theTree = new tree();
theTree.insert(10,25);
theTree.insert(20,1.75);
theTree.insert(75,1.02);
theTree.insert(5,1.01);

Node found = theTree.find(75);
if(found !=null){
S.O.P("Node founded");
}
else{
S.O.P("Node not found");
}
}
}

Deletion operation in Binary search tree

Deleting a node is a complicated operation in BST.

We can see three cases for deleting a node in BST. They are,

  1. The node to be deleted is a leaf.
  2. The node to be deleted has one child.
  3. The node to be deleted has two children.

 


Conclusion

With this I am concluding the article about tree data structure. If you like to learn about other data structures also please read them also. Doubly Linked List, The Queue Data Structure. We will meet soon again with another post. Till then goodbye to you all.

 

Audy Ranathunga

Audy Ranathunga, Author of myexamnote is our most experienced author. She has been working as a blog post writer for 4 years. She joined with myexamnote before 1 year ago and she has contribute lots of valuable posts for readers.

Leave a Reply