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.

 

Tree

A tree is a non linear data structure used to represent the data containing hierarchical relationship between the elements. Tree, a non-linear data structure, is a means to maintain and manipulate data in many applications.

In non-linear data structures, every data element may have more than one predecessor as well as successor. Non-linear data structures are capable of expressing more complex relationships than linear data structures.

A class of graphs that is acyclic is termed as trees.

The common uses of trees include the following:

1. Manipulating hierarchical data

2. Making information easily searchable

3. Manipulating sorted lists of data

Terminology of Trees

Root: A directed tree has one node called its root, with indegree zero.

Terminal node (leaf node): In a directed tree, any node that has an outdegree zero is a terminal node. The terminal node is also called as leaf node (or external node).

Branch node (internal node): All other nodes whose outdegree is not zero are called as branch nodes.

Level of node:  The level of any node is its path length from the root. The level of the root of a directed tree is zero, whereas the level of any node is equal to its distance from the root. Distance from the root is the number of edges to be traversed to reach the root.

 

1. A set of zero items is a tree, called the empty tree (or null tree).

2. The nodes with no subtrees are called terminal nodes or more commonly, leaves.

3. The degree of a node is the number of subtrees the node has.

4. The degree of a tree is the maximum degree of a node in the tree.

5. The length of a path is the number of edges it contains (which is one less than the number of nodes on the path).

6. The height of a tree is the length of the path from the root to a node at the lowest level. In other words, the height of a tree is the maximum path length in the tree.