Linked Implementation of Binary Trees

Binary tree has a natural implementation in a linked storage. Each node of a binary tree has both a left and a right subtree. Each node will have three fields—Lchild, Data, and Rchild.

 

In this node structure, Lchild and Rchild are the two link fields to store the addresses of left child and right child of a node; data is the information content of the node.

 

Here, 0 (zero) stored at Lchild or Rchild fields represents that the respective child is not present.

Advantages

The merits of representing binary trees through liked representations are as follows:

1. Like sequential representation, memory is not wasted.

2. Insertion and deletion operations are more efficient.

3. It is useful for dynamic data.

Disadvantages

The demerits of representing binary trees through linked representation are as follows:

1. In this representation, there is no direct access to any node. It has to be traversed from the root to reach to a particular node.

2. Having two link fields require more memory of node.

3. The programming languages not supporting dynamic memory management would not be useful for this representation.

Insertion of a node in Binary tree

The node to be inserted could be a branch node or a leaf node.

The insertion procedure is a two-step process:

1. Search for the node whose child node is to be inserted. This is a node will be parent node at level i, and a node is to be inserted at the level i + 1 as either its left child or right child.

2. Link a new node to the node that becomes its parent node, that is, either the Lchild or the Rchild.

Ex: Insertion of node G as the Rchild of node F

Array Implementation of Binary Trees

One of the ways to represent a tree using an array is to store the nodes level-by-level, starting from the level 0.

Let us consider the complete binary tree

Disadvantages

The various demerits when representing binary trees using arrays are as follows:

1. Other than full binary trees, majority of the array entries may be empty.

2. Dynamic resizing of array is not possible.

3. Insertion and deletions of new nodes is inefficient. ( Requires considerable data movement up and down the array, which demand excessive amount of processing time.)

Advantages

The various merits of representing binary trees using arrays are as follows:

1. Any node can be accessed from any other node by calculating the index.

2. No use of pointers.

Binary Tree

A binary tree

1. is either an empty tree or

2. consists of a node, called root, and two children, left and right, each of which is itself a binary tree.

 

Properties of a Binary Tree

1. There exists a unique path between every two vertices.

2. The number of vertices is one more than the number of edges in the tree. That is e = v-1

3. The sum of degrees of the vertices in any graph is equal to 2e. That is 2e=2v-2

4. The maximum number of nodes of level i in a binary tree is 2ⁱ⁻¹, where i ≥ 1.

5. The maximum number of nodes of depth d in a binary tree is 2^d−1, where d ≥ 1.

Binary Tree Abstract Data Type

class TreeNode

{

public:

char Data;

TreeNode *Lchild;

TreeNode *Rchild;

};

 

class BinaryTree

{

private:

TreeNode *Root;

public:

BinaryTree(){Root = Null};

// constructor creates an empty tree

TreeNode * GetNode();

void InsertNode(TreeNode*);

void DeleteNode( TreeNode*);

};

 

The basic operations on a binary tree can be as listed as follows:

1. Creation—Creating an empty binary tree to which the ‘root’ points

2. Traversal—Visiting all the nodes in a binary tree

3. Deletion—Deleting a node from a non-empty binary tree

4. Insertion—Inserting a node into an existing (may be empty) binary tree

5. Merge—Merging two binary trees

6. Copy—Copying a binary tree

7. Compare—Comparing two binary trees

8. Finding a replica or mirror of a binary tree

 

Realization of a Binary Tree

The implementation of a binary tree should represent the hierarchical relationship between a parent node and its left and right children.

Binary tree can be implemented as

-          Array implementation of a Binary tree

-          Linked implementation of a Binary tree

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.