This tutorial introduces a Binary Tree Data Structure in Java, both basic concept and its implementation in programming Java language. You know that one drawback of linked list is that data access is sequential and one of the disadvantages of using an array or linked list to store data is the time necessary to search for an item. Tree Data Structure is an improvement for that. Let’s learn and grow together.
Binary Tree Data Structure in Java
Tree Data Structure
A tree is a collection of nodes connected by directed (or undirected) edges. A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees. A tree has following general properties.
When we talk about tree, mostly we mean binary tree, that is a structure that has two children, left and right.
Binary Tree Representation
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
- Data
- Pointer to left child
- Pointer to right child
A pointer called ROOT points to the topmost node. Then the nodes that don’t have any children have their left and right pointers point to NULL.
We can represent a tree node in Java like this
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
/* Java Class has left and right child of current node and data value*/ class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } |
Implementation of Binary Tree Data Structure
Now, you can try to implement a Binary Tree Data Structure in Java language like below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/* Java Class has left and right child of current node and data value*/ class Node { int data; Node left, right; public Node(int item) { data = item; left = right = null; } } // A Java program to introduce Binary Tree class BinaryTreeDS { // Root node of tree Node root; // Constructors BinaryTreeDS(int data) { root = new Node(data); } BinaryTreeDS() { root = null; } public static void main(String[] args) { BinaryTreeDS tree = new BinaryTreeDS(); /*create root*/ tree.root = new Node(10); //create two children of root node tree.root.left = new Node(20); tree.root.right = new Node(30); //create a child of left element of root node tree.root.left.left = new Node(40); } } |
Here is output when you run the above program
Applications of trees
- Heap is a kind of tree that is used for heap sort.
- Compilers use a syntax tree to validate the syntax of every program you write.
- Manipulate hierarchical data.
- Router algorithms
- Manipulate hierarchical data.
