A tree is a data structure which consists of set of linked nodes to form a hierarchical tree structure.
A Simple Tree:
A -----------------------> level 0
/ \
B C -----------------------> level 1
/ \ / \
D E F G -----------------------> level 2
Tree can be used to represent file systems, hierarchy of an organisation etc.
What is a Binary Tree?
A Binary tree is a tree in which each node can have at most 2 children. The below diagram is an example for a binary tree. And the node A has two children B and C. B has one right child and C has one left child. No node in this tree has more than two children.
A
/ \
B C
\ /
E F
Maximum height of binary tree with n nodes is at most n-1.
A
\
B
/
C
\
D
The above tree has 4 nodes and its height is 3.
Minimum height of a binary tree:
Consider a binary tree of height h and it has at most 2^i nodes at level i.
A -------> Level 0
/ \
B C -------> Level 1
\ /
E F --------> Level 2
No of leaves <= 1+no of internal nodes
Level of A is 0 and it has 1 node (2^0)
Level 1 has 2 nodes B and C.
Level 2 has only 2 nodes.
So, the number of nodes in a binary tree <= 1+ 2^1 + 2^2 + ... + 2^h
no of nodes in binary tree (n) <= 2^(h+1) -1
n <= 2^(h+1) - 1
n+1 <= 2^(h+1)
n+1 <= 2^h * 2
(n+1)/2 <= 2^h
(logbase2)(n+1)/2 <= h
h >= (logbase2)(n+1)/2
Representation Of Arithmetic Expression Using Binary Tree:
Arithmetic Expression: (D * E) + (F - G)
+
/ \
* -
/ \ / \
D E F G
Full Binary Tree:
A full binary tree is a tree in which every nodes other than leaf nodes has two children.
A -----------------------> level 0
/ \
B C -----------------------> level 1
/ \ / \
D E F G -----------------------> level 2
No of nodes at level i = 2^i
level 2 has 4(2^2) nodes D, E, F and G.
No of leaves at height h = 2^h
height 2 has 4 (2^2) nodes D, E, F and G.
No of internal nodes = 1 + 2^1 + 2^2 + ... + 2^(h-1) = 2^h - 1
No of internal nodes for the above tree is 3 (2^2 -1).
No of leaves in a tree of n nodes = (number of nodes in the tree+1) / 2
= (7+1)/2 => 4
See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs
A Simple Tree:
A -----------------------> level 0
/ \
B C -----------------------> level 1
/ \ / \
D E F G -----------------------> level 2
- Here, A is the root node. A root node is a node which has no parent.
- B, C are children of A.
- B, C are siblings.
- D and E are children of B. F and G are children of C.
- D, E are siblings. F,G are siblings.
- D, E, F and G are leaf nodes. A node which has no children is leaf node.
- A, B, C are internal nodes. A node which has no leaf is an internal node.
- The depth of D, E, F and G is 2 (depth <=> level).
- Height of a tree is the maximum level of any node in the tree. Here, the height of the tree is 2.
- And the degree is the number of children present to a node. The degree of node A is 2.
Tree can be used to represent file systems, hierarchy of an organisation etc.
What is a Binary Tree?
A Binary tree is a tree in which each node can have at most 2 children. The below diagram is an example for a binary tree. And the node A has two children B and C. B has one right child and C has one left child. No node in this tree has more than two children.
A
/ \
B C
\ /
E F
Maximum height of binary tree with n nodes is at most n-1.
A
\
B
/
C
\
D
The above tree has 4 nodes and its height is 3.
Minimum height of a binary tree:
Consider a binary tree of height h and it has at most 2^i nodes at level i.
A -------> Level 0
/ \
B C -------> Level 1
\ /
E F --------> Level 2
No of leaves <= 1+no of internal nodes
Level of A is 0 and it has 1 node (2^0)
Level 1 has 2 nodes B and C.
Level 2 has only 2 nodes.
So, the number of nodes in a binary tree <= 1+ 2^1 + 2^2 + ... + 2^h
no of nodes in binary tree (n) <= 2^(h+1) -1
n <= 2^(h+1) - 1
n+1 <= 2^(h+1)
n+1 <= 2^h * 2
(n+1)/2 <= 2^h
(logbase2)(n+1)/2 <= h
h >= (logbase2)(n+1)/2
Representation Of Arithmetic Expression Using Binary Tree:
Arithmetic Expression: (D * E) + (F - G)
+
/ \
* -
/ \ / \
D E F G
Full Binary Tree:
A full binary tree is a tree in which every nodes other than leaf nodes has two children.
A -----------------------> level 0
/ \
B C -----------------------> level 1
/ \ / \
D E F G -----------------------> level 2
No of nodes at level i = 2^i
level 2 has 4(2^2) nodes D, E, F and G.
No of leaves at height h = 2^h
height 2 has 4 (2^2) nodes D, E, F and G.
No of internal nodes = 1 + 2^1 + 2^2 + ... + 2^(h-1) = 2^h - 1
No of internal nodes for the above tree is 3 (2^2 -1).
No of leaves in a tree of n nodes = (number of nodes in the tree+1) / 2
= (7+1)/2 => 4
See Also:
C Program To Represent Binary Search Tree Using Arrays
C Program To Perform Insertion, Deletion and Traversal In Binary Search Tree
C Program To Implement Binary Tree Traversals: In-order, Pre-order and Post-order
C Program To Implement Dictionary Using Binary Search Tree
C Program To Perform Searching in Binary Search Tree
C Program To Perform Insertion, Deletion And Traversal In Red Black Tree
C Program To Perform Insertion, Deletion and Traversal in AVL Tree
C Program To Perform Insertion, Deletion and Traversal In B-Tree
C Program To Implement Priority Queue Using Binary Heaps
Construct Binary Search Tree From In-order and Pre-order Traversal Outputs
No comments:
Post a Comment