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