A tree is an abstract data type (ADT) or data structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes. In computer science, trees are widely used to represent data that has a hierarchical structure, such as file systems, organization charts, and family trees.
Basic Terminologies of Trees
Node
A node is a fundamental part of a tree that contains data and a reference (or pointer) to its child nodes. The topmost node of a tree is called the root node. A node can have zero or more child nodes.
Degree
The degree of a node is the number of its child nodes. For example, a node with no children has a degree of 0, while a node with three children has a degree of 3.
Level
The level of a node indicates its distance from the root node. The root node is at level 1, its children are at level 2, their children are at level 3, and so on.
Height
The height of a tree is the length of the longest path from the root node to any leaf node. In other words, it is the number of levels in the tree.
Parent and Child
A node that has a child node is called the parent of that child node. Conversely, a node that has a parent node is called a child node of that parent. For example, if Node A has Node B as its child, then Node A is the parent of Node B, and Node B is the child of Node A.
Ancestor and Descendant
A node is said to be an ancestor of all the nodes in its subtree. Conversely, a node is said to be a descendant of all the nodes in its parent chain. For example, if Node A has Node B as its child, and Node B has Node C as its child, then Node A is an ancestor of Node C, and Node C is a descendant of Node A.
Leaf Node
A leaf node is a node that does not have any child nodes. It is also known as a terminal node or a external node. Leaf nodes can be located at any level of a tree.
Binary Tree:
Has Two nodes only at most. Though, it can have one node only as well. Or, can have no node and that will be called the leave node.
So, the degree of the binary node is 2.
You can't remove the root node.
Full Binary Tree:
A tree of height h which has all leaf nodes at level h.
All non-leaf nodes has exactly 2 children.
Complete Binary Tree
Binary tree at all levels of which, except last, has as many nodes as possible.
Nodes on last level are filled from left to right.
Balanced Binary Tree.
The heights of left and right subtrees differs by no more than 1
Leftist(rightist) Binary Tree.
A binary tree where all interior nodes have either only left(right) subtree.
Binary Tree - Traversal(visitation of node)
If anyone asks you on how do you traverse through the binary tree, you can think of three ways. Those are listed below:
Pre-order traversal:
Visit node r
Traverse the left sub-tree in pre-order
Traverse the right sub-tree in pre-order
Resulting sequence: parent, left child, right child
private void postorderTraverse(BinaryNode<T> node) {
if (node != null) {
// Traverse the left sub-tree in post-order
postorderTraverse(node.getLeftChild());
// Traverse the right sub-tree in post-order
postorderTraverse(node.getRightChild());
// Visit the node
System.out.println(node.getData());
}
}
public void postorderTraverse() {
// Start the traversal from the root node
postorderTraverse(root);
}
In-order traversal:
Traverse the left sub-tree in in-order
Visit node r
Traverse the right sub-tree in in-order
Resulting sequence: left child, parent, right child
public void inorderTraverse() {
inorderTraverse(root);
} // end inorderTraverse
private void inorderTraverse(BinaryNode<T> node) {
if (node != null) {
inorderTraverse(node.getLeftChild());
System.out.println(node.getData());
inorderTraverse(node.getRightChild());
} // end if
} // end inorderTraverse
Post-order traversal:
Traverse the left sub-tree in post-order
Traverse the right sub-tree in post-order
Visit node r
Resulting sequence: left child, right child, parent
private void postorderTraverse(BinaryNode<T> node) {
if (node != null) {
// Traverse the left sub-tree in post-order
postorderTraverse(node.getLeftChild());
// Traverse the right sub-tree in post-order
postorderTraverse(node.getRightChild());
// Visit the node
System.out.println(node.getData());
}
}
public void postorderTraverse() {
// Start the traversal from the root node
postorderTraverse(root);
}
Binary Search Tree
bstSearch (binarySearchTree, desiredObject) {
// Searches a binary search tree for a given object.
// Returns true if the object is found.
if (binarySearchTree is empty)
return false
else if (desiredObject == object in the root of binarySearchTree)
return true
else if (desiredObject < object in the root of binarySearchTree)
return bstSearch(left subtree of binarySearchTree, desiredObject)
else
return bstSearch(right subtree of binarySearchTree, desiredObject)
}