4.introduction toDS - Algorithms - Day4 PDF
4.introduction toDS - Algorithms - Day4 PDF
4.introduction toDS - Algorithms - Day4 PDF
– Terminology of Trees:
• Node (also called a Leaf): is any data item in the tree.
• Root Node(also called Parent Node) : is the first item in the tree.
• Tree Height: is equal to the number of layers deep that its root grows.
N nodes = 6
N – 1 edges= 5
Tree Height = 3
– Terminology of Trees:
• A path from node n1 to nk is defined as a sequence of nodes n1, n2, …, nk
such that ni is parent of ni+1 (1 ≤i < k)
• The depth of node ni is the length of the path from root to node ni
• The height of node ni is the length of longest path from node ni to a leaf.
– Binary Trees are special type of Trees because, when they are sorted,
they lend themselves to rapid searches, insertions, and deletions.
3 5 7
– Full Binary Tree of height h, all nodes that are at a level less than h
have two children each.
– Each node in a full binary tree has left and right subtrees of the same
height.
– Among binary trees of height h, a full binary tree has as many leaves
as possible, and they all are at level h.
– A binary tree is height balanced (or balanced), if the height of any node’s right
subtree differs from the height of the node’s left subtree by no more than 1.
5
1
4 6
2
4
2
3 5 6
2 6
5
1 3
– Method 2: Preorder.
– Method 3: Postorder.
• Deleting Nodes
– Case 1: delete a leaf node.
class Employee
{ :
:
int Code;
public:
Employee *pRight;
Employee *pLeft;
};
class BinaryTree{
Employee *pParent;
Employee *insert(Employee *pRoot, Employee *data);
void inOrder(Employee *pRoot);
void preOrder(Employee *pRoot);
void postOrder(Employee *pRoot);
Employee * deleteT(Employee *pRoot, int key );
int getHeight(Employee *pRoot);
public:
Binary(); { pParent = NULL; }
void insertNode(Employee *data);
Employee *searchTree(int code);
void inOrderTraverse();
void preOrderTraverse();
void postOrderTraverse();
void deleteNode(int key );
int getTreeHeight();
}
5 5 5 5
8 2 8 2 8
}
Call
inOrderTraverse()
}
Call
preOrderTraverse ()
}
Call
postOrderTraverse ()
Y=4
5
X=2 Y=3
2 7
Y=1 Y=2
0 0
4 9
X=1
0
0 0
8
0 0
50 50
40 60 40 60
30 45 70 30 45
50 50
40 60 40 70
30 45 70 30 45
50 45 60
40 60 40 60 40 70
30 45 70 30 70 30 45
}
JavaTM Education & Technology Services
Copyright© Information Technology Institute http://jets.iti.gov.eg 31
Binary Trees
……..// 2
45
}
JavaTM Education & Technology Services
Copyright© Information Technology Institute http://jets.iti.gov.eg 32
Binary Trees
……..// 3 55 70
}
40
45
JavaTM Education & Technology Services
Copyright© Information Technology Institute http://jets.iti.gov.eg 33
Binary Trees
• 1st Assignment :
• Implement the functions explained on Binary Tree in Lecture.
• Bonus:
– Implement DeleteNode () function on Binary Tree.
– Implement a function that will count the leaves of a binary tree.
• Search :
– Binary Search tree