Tree is a collection of one or more nodes.
Example:
The degree of tree is 3. Height is the same as degree of tree. The topmost node is called as root. The line that connect the nodes are called edge. Nodes that have children are called parents and children with same parent are called sibling. Nodes that have no children are called leaf.
Binary Tree
Binary tree is a tree that each node has at most two children. Maximum number of nodes on level k of a binary tree is 2k. Maximum number of nodes on binary tree height is 2h+1 -
1. Minimum height of a binary tree of n nodes is 2log(n). Maximum height of binary tree of n nodes is n-1.
There are four types of binary tree. Those are:
- Perfect binary tree
Perfect binary tree is a binary tree that all levels are full filled. Every parent nodes has two children.
- Complete binary tree
Complete binary tree is a binary tree that all levels are full filled except the last level may not be full filled. A perfect binary tree is also a complete binary tree.
- Skewed binary tree
Skewed binary tree is a binary tree which each node has at most one child.
- Balanced binary tree
Balanced binary tree is a binary tree which has the same amount of leaf in the right and left side.
Implementation Using Array
Index on array represents node number.
Index 0 is root node.
Index left child is 2p+1.
Index right child is 2p+2.
Index parent is (p-1)/2.
p is parent index.
Implementatiton Using Linked List
Expression Tree Concept
Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)
How to read:
Prefix: read from the root then go down to the left side until the leaf on the left side. Continue with the right node.
Postfix: read from the most left bottom. Continue to the right node.
Infix: read from the left to right.
Tidak ada komentar:
Posting Komentar