Overview
- Binary Tree
- Complete Binary tree
- Almost complete Binary tree
- Strict Binary Tree
- Representation of Binary three
Binary Tree
- A binary tree is defined as a finite set of elements ,called nodes, such that
- T is empty (called the Nulltree or empty tree) , or
- T contains a distinguished node R,called the root of T,
and the remaining nodes ofT form an ordered pair of disjoint binarytrees
T1 and Tz
- Any node in the binary tree has either 0 , I or 2 child nodes.
Complete Binary Tree
- completeBinarytree.AM levels are completely filled
Almost Complete Binary Tree
- All levels are completely filled,except possibily the last level and nodes in the last level are all left alinged.
Strict Binary Tree
- Each node of a strict binary tree will have either 0 or 2 children.
Representation of Binary Tree
- There are two possible representations of binary tree
① Array Representation
② Linked Representation ( by default)
Array Representation
Linked Representation
Node:
Root:
- root is a node reference
- when root contains null ,tree is empty.
Discuss
- How to insert an item in a BT?
- How to traverse a BT ?
Insert an elements in BT
Traversing
- ptr.getitem();
ptr=ptr.getleft();
ptr=stack.pop()
Logic to traverse a BT
- Iterative method
- Recursive method
- Preorder R T,Tz
② Inorder T R T2
③ postorder T1 T2 R
- Preorder R T,Tz
