- A binary tree is a tree in which no node can have more than two children.These children are described as left child and right child of the parent node.
- A binary tree T is defined as a finite set of nodes such that

- T is empty (ie) T has no nodes called the null tree or empty tree.
- There is a specially designated node called the root of the tree, and the remaining nodes are partitioned in to two disjointed sets T
_{1}and T_{2},each of which is a binary tree.T_{1}is called the left subtree and T_{2}is called the right subtree.

- Example of a binary tree is shown in figure 1

- In the above binary tree A is the root node of the binar tree.B is the left child of A and C is the right child of A. So A is the parent node of B and C. B and C are the children of A.
- If a node has no child then its called a leaf node. In the above example nodes D,H,I,F,J are leaf nodes
- For a binary tree the
**maximum number of nodes at level i**will be**2**considering root node is at level 0.^{i} - If K is the depth of the tree then the
**maximum number of nodes**that the tree can have is**2**^{K}-1

__Strictly binary tree:__- The tree is said to be strictly binary tree, if every non-leaf node in a binary tree has non-empty left and right sub trees
- (ie) every node in the strictly binary tree contains either no children or 2 children.
- figure 1 is not a strictly binary tree because node G has only one child
- A
**strictly binary tree with n leaves always contains 2n-1 nodes**. The strictly binary tree in the below figure has 5 leaves such as D,E,F,H,I. here n=5.so the tree has 2*5-1 ie 9 nodes.The tree contains 9 nodes only.So in strictly binary tree given the number of leaves we can easily find the totla number of nodes in the tree. - Strictly binary tree is also called
**2-tree**or**extended binary tree**.

- The main application of a 2-tree is to represent any algebraic expression such as [E=(a+b)/((c-d)*e)]using binary operation
**.**

## No comments:

## Post a Comment