Types of Trees

 

Free tree: A free tree is a connected, acyclic graph. It is an undirected graph. It has no node designated as a root. Any node can be reached from any other node through a unique path.

 

Rooted tree: A rooted tree is a directed graph where one node is designated as root node.

 

Ordered tree: It is a directed tree, in which each node has an ordering at each level.

 

Regular tree: A tree where each branch node vertex has the same outdegree is called a regular tree.

If in a directed tree, the outdegree of every node is less than or equal to m, then the tree is called an m-ary tree.

If the outdegree of every node is exactly equal to m (the branch nodes) or zero (the leaf nodes), then the tree is called a regular m-ary tree.

Binary tree: A binary tree is a special form of an m-ary tree where m=2. In a binary tree, no node has more than two children.

Complete tree: A tree with n nodes and of depth k is complete if and only if its nodes correspond to the nodes that are numbered from 1 to n in the full tree of depth k.

A binary tree of height h is complete if and only if one of the following holds good:

1. It is empty.

2. Its left subtree is complete of height h - 1 and its right subtree is completely full of height h - 2.

3. Its left subtree is completely full of height h - 1 and its right subtree is complete of height h - 1.

A binary tree is completely full if it is of height h and has (2^h+1 - 1) nodes.

Full binary tree: A binary tree is a full binary tree if it contains the maximum possible number of nodes in all levels.

In a full binary tree, each node has two children or no child at all. The total number of nodes in a full binary tree of height h is 2^h+1 - 1 considering the root at level 0.

 Complete binary tree: A binary tree is said to be a complete binary tree if all its levels except the last level have the maximum number of possible nodes, and all the nodes of the last level appear as far left as possible.

Strictly binary tree: If every non-terminal node in a binary tree consists of non-empty left and right subtrees, then such a tree is called a strictly binary tree.

Position tree: Also known as suffix tree, is one that represents the suffixes of a string S. Suffix trees allows fast implementations of string operations.