Tree:::

A Tree t is a finite non empty set of elements one of these elements is called root. And the remaining elements are partioned into subtrees of t.

Degree of an element :::

The no of children the element has.

Degree of the tree:::

The maximum of degrees of its elements.

Level:::

The level of the root is 0 and the level of any node is one more than its parent.

Height:::

The height of a binary tree is the no. of levels in it.

Binary Tree :::

A Binary tree is a finite set of elements posibbly empty.When binary tree is not empty ,it has a root element the remaining elements are partitioned in to two binary trees.

Trees | Binary Trees

______________________|_______________________

1.Non empty set. | 1.Can be empty.

2.Can have any no. | 2.Maximum two decendents

of decendents |

Example of a tree ::

The essential differences between a tree and a binary tree:::

-> A Binary tree can be empty, but a tree can’t.

-> Each element in a binary tree has exactly two subtrees(one or both of these may be empty).Each element in a tree can have any no. of subtrees.

-> The subtrees of each element in a binary tree are ordered i.e. we distinguish between left and right subtrees.

Properties of binary tree:::

1) The binary Tree with ‘n’ elements has exactly n-1 edges.

2) A Binary Tree of height ‘h’ ,h>0 has atleast h and at most 2^h-1 elements in it.

3) The height of a binary tree that contains n(n>=0) elements is at least equal to ceil( log with base2 (n+1) ) and at most equal to n.

Full Binary Tree:::

A binary tree of height h that contains exactly 2^h -1 elements is called a full binary tree.

Complete Binary Tree:::

A Complete Binary Tree is a binary Tree in which all the leaves are at the same level.

A Binary of height h is a complete binary tree if and only if

1) Any node at level less than h-1 has two children.

2) Let i,1<=i<=n ,be the number assigned to an element of a complete binary tree . The following are true.

i) If i=1, then this element is the root of the complete binary tree.

If i>1, then the parent of this element is assigned with number flore(i/2).

ii) If 2i>n then this element has no left tree, otherwise , its legt chaild has been assigned the number 2i.

iii) If 2i+1 > n , then this element has no left chaild ,otherwise its left child has been assigned the number 2i+1.

Binary tree traversals :::

1)Pre order traversal

2)Post order traversal

3)In order traversal

-> Pre order traversal :::

In this type of traversal the root is visited first and then the left subtree is visited and then right sub tree is visited.

An example program is given in the following link

preorder_traversal

-> In order traversal :::

In this type of traversal the left subtree is visited first and then the root is visited and then right sub tree is visited.

An example program is given in the following link

postorder_traversal

-> In order traversal :::

In this type of traversal the left sub treeroot is visited first and then the right subtree is visited and then root is visited.

An example program is given in the following link

inorder_traversal

Thanks for sharing this information. Really is pack with new knowledge. Keep them coming.