Table of contents
Binary trees are a fundamental data structure in computer science, often used for searching and sorting algorithms. They are a tree-like data structure where each node can have at most two children, referred to as the left and right children.
Here is a diagram of a binary tree:
8
/ \
/ \
/ \
/ \
5 10
/ \ / \
2 6 9 12
In the above diagram, the node with the value 8 is the root node of the tree. The nodes with the values 5 and 10 are its children, and so on. Each node in the tree can be thought of as a separate tree in itself, with its own set of children.
The advantage of using a binary tree is that it allows for fast searching, insertion, and deletion. Because each node has at most two children, the height of the tree is logarithmic in the number of nodes, resulting in efficient algorithms.
Here is an implementation of a Node class in Dart:
class Node<T> {
T data;
Node<T>? left;
Node<T>? right;
Node({required this.data});
}
In the above code, we have defined a generic class Node with three properties: data, left, and right. The data holds the value of the current node, and the left and right properties hold the references to the left and right child nodes respectively.
Here is an implementation of the abstract class Tree
abstract class Tree<T> {
Node<T> _insert(Node<T>? node, T data);
bool _search(Node<T>? node, T data);
void _inOrderTraversal(Node<T>? node);
void _postOrderTraversal(Node<T>? node);
void _preOrderTraversal(Node<T>? node);
}
The above code is an abstract class called Tree that defines a generic type T. This class contains several methods that are related to the operations that can be performed on a tree data structure such as insert, search, inorder traversal, postorder Traversal, and preorder Traversal.
The _insert method takes in two parameters: a node of type Node<T> and data of type T. This method is responsible for inserting a new node into the tree with the given data.
The _search method takes in two parameters: a node of type Node<T> and data of type T. This method is responsible for searching for a specific node in the tree with the given data.
The _inOrderTraversal method takes in a single parameter: a node of type Node<T>. This method is responsible for traversing the tree in an in-order fashion, visiting the left subtree first, then the root, and finally the right subtree.
The _postOrderTraversal method takes in a single parameter: a node of type Node<T>. This method is responsible for traversing the tree in a post-order fashion, visiting the left subtree first, then the right subtree, and finally the root.
The _preOrderTraversal method takes in a single parameter: a node of type Node<T>. This method is responsible for traversing the tree in a pre-order fashion, visiting the root first, then the left subtree, and finally the right subtree.
It is important to notice that all the methods are marked as abstract, this means that these methods are not implemented in this class and must be implemented in a derived class.
Now, let's define the Binary Tree class and some operations that can be performed on a binary tree.
class BinaryTree<T extends Comparable> implements Tree<T> {
Node<T>? root;
//some operation..
}
The class BinaryTree<T extends Comparable> is a generic class that implements the Tree<T> interface. The generic type T is constrained to types that extend the Comparable class, which means that the type must have a compareTo method defined. This is used in the insert and search methods to compare the data of nodes in the tree.
The class has a nullable property root of type Node<T>? which is the root of the binary tree.
The class BinaryTree implementation of Tree abstract class which means it has to implement all the methods of the tree interface.
Insert:
void insert(T data) {
root = _insert(root, data);
}
@override
Node<T> _insert(Node<T>? node, T data) {
if (node == null) {
return Node(data: data);
}
if (data.compareTo(node.data) <= 0) {
node.left = _insert(node.left, data);
} else {
node.right = _insert(node.right, data);
}
return node;
}
The insert() is used to insert new data into the binary tree. This method uses the private helper method _insert() to recursively find the correct location to insert the new data. If the current node is null, a new node with the data is returned. Otherwise, the compareTo() is used to compare the data to the data of the current node. If the data is less than or equal to the current node's data, the left property is updated with the result of calling _insert() on the left child node. Otherwise, the right property is updated with the result of calling _insert() on the right child node.
Search:
bool search(T data) {
return _search(root, data);
}
@override
bool _search(Node<T>? node, T data) {
if (node == null) {
return false;
}
if (node.data == data) {
return true;
}
if (data.compareTo(node.data) <= 0) {
return _search(node.left, data);
} else {
return _search(node.right, data);
}
}
The search() is used to search for a specific piece of data in the binary tree. Like the insert() method, this method uses a private helper method _search() to recursively search the binary tree.
If the current node is null, the data is not in the binary tree and false is returned. If the current node's data is equal to the search data, true is returned.
Otherwise, the compareTo() is used to determine if the search data is less than or greater than the current node's data.
If the search data is less than the current node's data, _search() is called on the left child node. Otherwise, _search() is called on the right child node.
In-order, Pre-order & Post-order Traversal:
void inOrderTraversal() {
_inOrderTraversal(root);
}
void preOrderTraversal() {
_preOrderTraversal(root);
}
void postOrderTraversal() {
_postOrderTraversal(root);
}
@override
void _inOrderTraversal(Node<T>? node) {
if (node != null) {
_inOrderTraversal(node.left);
print(node.data);
_inOrderTraversal(node.right);
}
}
@override
void _postOrderTraversal(Node<T>? node) {
if (node != null) {
print(node.data);
_postOrderTraversal(node.left);
_postOrderTraversal(node.right);
}
}
@override
void _preOrderTraversal(Node<T>? node) {
if (node != null) {
_preOrderTraversal(node.left);
_preOrderTraversal(node.right);
print(node.data);
}
}
he inOrder(), preOrder(), and postOrder() methods are used to traverse the binary tree and print out the data in the nodes.
Each of these methods uses a private helper method with the same name but with a leading underscore, such as _inOrder(), to recursively traverse the binary tree.
The inOrder() first recursively calls itself on the left child node, then prints the current node's data, and finally recursively calls itself on the right child node.
The preOrder() method prints the current node's data, recursively calls itself on the left child node, and finally recursively calls itself on the right child node.
The postOrder() method recursively calls itself on the left child node, recursively calls itself on the right child node, and finally prints the current node's data.
here is an implementation full code of Binary tree:
class Node<T> {
T data;
Node<T>? left;
Node<T>? right;
Node({required this.data});
}
abstract class Tree<T> {
Node<T> _insert(Node<T>? node, T data);
bool _search(Node<T>? node, T data);
void _inOrderTraversal(Node<T>? node);
void _postOrderTraversal(Node<T>? node);
void _preOrderTraversal(Node<T>? node);
}
class BinaryTree<T extends Comparable> implements Tree<T> {
Node<T>? root;
void insert(T data) {
root = _insert(root, data);
}
@override
Node<T> _insert(Node<T>? node, T data) {
if (node == null) {
return Node(data: data);
}
if (data.compareTo(node.data) <= 0) {
node.left = _insert(node.left, data);
} else {
node.right = _insert(node.right, data);
}
return node;
}
bool search(T data) {
return _search(root, data);
}
@override
bool _search(Node<T>? node, T data) {
if (node == null) {
return false;
}
if (node.data == data) {
return true;
}
if (data.compareTo(node.data) <= 0) {
return _search(node.left, data);
} else {
return _search(node.right, data);
}
}
void inOrderTraversal() {
_inOrderTraversal(root);
}
void preOrderTraversal() {
_preOrderTraversal(root);
}
void postOrderTraversal() {
_postOrderTraversal(root);
}
@override
void _inOrderTraversal(Node<T>? node) {
if (node != null) {
_inOrderTraversal(node.left);
print(node.data);
_inOrderTraversal(node.right);
}
}
@override
void _postOrderTraversal(Node<T>? node) {
if (node != null) {
print(node.data);
_postOrderTraversal(node.left);
_postOrderTraversal(node.right);
}
}
@override
void _preOrderTraversal(Node<T>? node) {
if (node != null) {
_preOrderTraversal(node.left);
_preOrderTraversal(node.right);
print(node.data);
}
}
}
In conclusion, binary trees are a powerful and versatile data structure with many uses in computer science. They allow for efficient searching, insertion, and deletion, and their logarithmic height makes them well-suited for algorithms that require fast performance. Understanding binary trees is essential for understanding more complex data structures and algorithms.