Transcript Lecture - Binary Tree - Home

(1)
Data Structures – CSC212
Binary Tree ADT
It is an ordered tree with the following properties
1. Each node can have at most two subtrees
2. Each subtree is identified as being either left
subtree or the right subtree of its parent
3. It may be empty
Note:
 Property 1 says that each node can have maximum two
children
 The order between the children of a node is specified by
labeling its children as left child and right child
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(2)
Data Structures – CSC212
Why binary Trees?
 Binary trees naturally arise in many different applications
1. Expression Tree
- A central data structure in compiler design
- Interior nodes contain operators and the leaf nodes have operands
- An expression is evaluated by applying the operator at root to the
values obtained by recursively evaluating the left and right subtrees
- The following tree corresponds the expression: (a+((b-c)*d)
+
*
a
b
Dr Muhammad Hussain
d
c
Lecture - Binary Tree ADT
(3)
Data Structures – CSC212
Why binary Trees?
2. Huffman Coding Tree
- Its is used in a simple but effective data compression algorithm
- In this tree, each symbol is stored at a leaf node
- To generate the code of a symbol traverse the tree from the root to
the leaf node that contains the symbol such that each left link
corresponds to 0 and each right link corresponds to 1
- The following tree encodes the symbols a, b, c, d
0
1
a
1
0
0
b
d
1
c
The code of a is 0, and that of b is 100
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(4)
Data Structures – CSC212
Recursive definition of Binary Tree
A binary tree is
- empty OR
- a node, called the root node, together with two binary
trees, which are disjoint from each other and the root
node. These are called left and right subtrees of the root
 Many routines can be efficiently implemented using recursive nature of the binary tree
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(5)
Data Structures – CSC212
Types of Binary Tree
Full - Every node has exactly two children in all levels,
except the last level. Nodes in last level have 0
children
Complete - Full up to second last level and last level is
filled from left to right
Other - not full or complete
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(6)
Data Structures – CSC212
Full,
Complete
or Other?
B
I
J
K
Dr Muhammad Hussain
not binary
A
C
H
L
M
T
S
D
G
F
E
O
N
R
Q
P
Lecture - Binary Tree ADT
(7)
Data Structures – CSC212
Full,
Complete
or other?
A
B
I
K
Dr Muhammad Hussain
D
H
L
M
T
S
G
F
O
N
R
P
Lecture - Binary Tree ADT
(8)
Data Structures – CSC212
Full,
Complete
or other?
A
B
L
T
Dr Muhammad Hussain
G
H
I
K
D
F
O
N
M
S
R
Lecture - Binary Tree ADT
P
(9)
Data Structures – CSC212
Full,
Complete
or other?
A
B
T
Dr Muhammad Hussain
L
S
G
H
I
K
D
M
F
O
N
R
P
Lecture - Binary Tree ADT
(10)
Data Structures – CSC212
Full,
Complete
or other?
A
B
T
Dr Muhammad Hussain
G
H
I
K
D
L
M
N
O
F
R
S
Lecture - Binary Tree ADT
P
(11)
Data Structures – CSC212
Full,
Complete
or Other?
A
T
Dr Muhammad Hussain
G
H
I
K
D
B
L
M
N
O
P
F
Q
S
Lecture - Binary Tree ADT
R
(12)
Data Structures – CSC212
Full,
Complete
or other?
A
G
H
I
K
D
B
L
M
O
N
T
Dr Muhammad Hussain
P
F
Q
S
Lecture - Binary Tree ADT
R
(13)
Data Structures – CSC212
Full,
Complete
or Other?
A
Dr Muhammad Hussain
G
H
I
K
D
B
L
M
N
O
P
F
Q
Lecture - Binary Tree ADT
R
(14)
Data Structures – CSC212
Binary Tree Traversal
Process
To process a node means to perform some simple operation like printing the
contents of the node or updating the contents of the node
Traversal
To traverse a finite collection of objects means to process each object in the
collection exactly once
Examples
1. List traversal – to process each element of list exactly once
2. Tree traversal – to process each node of tree exactly once
Dr Muhammad Hussain
Lecture - Binary Tree ADT
Data Structures – CSC212
(15)
Traversal Of Binary Tree
There are four methods for the traversal of a binary tree
1. Preorder Traversal
Each node is processed before any node in either of its subtrees
2. Inorder Traversal
Each node is processed after all nodes in its left subtree and before any node in
its right subtree
3. Postorder Traversal
Each node is processed after all nodes in both of its subtrees
4. Level order Traversal
Each node at level l is processed before any node at level l+1
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(16)
Data Structures – CSC212
Preorder Traversals
1.
2.
3.
Visit the root
Visit Left subtree
Visit Right subtree
1
A
B
2
5
L
T
6
Dr Muhammad Hussain
G
12
H
8
3I
K
4
11
D
F
13
O
14
N
10
M
9
S7
R
15
16
P
Lecture - Binary Tree ADT
(17)
Data Structures – CSC212
Algorithm TraversePreorder(n)
Process node n
if n is an internal node then
TraversePreorder( n -> leftChild)
TraversePreorder( n -> rightChild)
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(18)
Data Structures – CSC212
Inorder Traversals
1.
2.
3.
Visit Left subtree
Visit the root
Visit Right subtree
10
1A
6B
1
4
L
T
3
Dr Muhammad Hussain
G
11
8
H
2I
1
K
1
12
D
16
F
14
O
N9
M
7
5
S
13
R
15
P
Lecture - Binary Tree ADT
(19)
Data Structures – CSC212
Algorithm TraverseInorder(n)
if n is an internal node then
TraverseInorder( n -> leftChild)
Process node n
if n is an internal node then
TraverseInorder( n -> rightChild)
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(20)
Data Structures – CSC212
Postorder Traversals
1.
2.
3.
Visit Left subtree
Visit Right subtree
Visit the root
A
16
9
B
L
4
2
3
T
2
Dr Muhammad Hussain
G
10
H
8
2
5I
K
1
D
15
14
F
13
O
7
N
M
6
S
3
R
11
12
P
Lecture - Binary Tree ADT
(21)
Data Structures – CSC212
Algorithm TraversePostorder(n)
if n is an internal node then
TraversePostorder( n -> leftChild)
TraversePostorder( n -> rightChild)
Process node n
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(22)
Data Structures – CSC212
Level Order Traversals
1.
2.
3.
4.
Visit the root
Visit root of Left subtree
Visit root of Right subtree
???
B
4
9
H
15
M
Dr Muhammad Hussain
B
2
D
3
G
7
H
6
5I
K
10
N
16
A
1
11
L
T
17
8F
14
O
13
N
M
12
S
18
R
19
20
P
Lecture - Binary Tree ADT
(23)
Data Structures – CSC212
Specification of Binary Tree ADT
Elements: Any data type
Structure: A binary tree either is empty OR a node, called the root node,
together with two binary trees, which are disjoint from each
other and the root node. These are called left and right
subtrees of the root
Domain: Number of elements is bounded
Operations:
Operation
Specification
void empty()
Precondition/Requires: none.
Processing/Results: returns true if the binary tree (BT) has no nodes.
void traverse(Order
ord)
Precondition/Requires: BT is not empty.
Processing/Results: Traverses the binary tree according to the value of ord
(1) ord = preOrder: traverses the tree using preorder traversal
(2) ord = inOrder: traverses the tree using inorder traversal
(3) ord = postOrder: traverses the tree using postorder traversal
Dr Muhammad Hussain
Lecture - Binary Tree ADT
Data Structures – CSC212
(24)
Operation
Specification
void find (Relative
rel)
Precondition/Requires: BT is not empty.
Processing/Results: the current node of BT is determined by Relative and the
current node prior to the operation as follows (always return true unless
indicated so):
(1) rel = Root: current = root
(2) rel = Parent: if the current node has a parent then parent is the current node;
otherwise returns false
(3) rel = LeftChild: if the current node has a leftchild then it will be the current
node; otherwise returns false
(4) rel = RightChild: same as above but for rightchild.
void insert(Relative
rel, Type val)
Precondition/Requires: either (1) BT is empty and rel = Root; or (2) BT not
empty and rel  Root .
Processing/Results: as follows:
(1) rel = Root: create a root node with data = val.
(2) rel = Parent: nonsense case.
(3) rel = LeftChild: if current node does not have a leftchild then make one with
data = val.
(4) rel = RightChild: same as above but for rightchild.
In all the above cases if the insertion was successful then it will be designated
as current node and returns true, otherwise current remains unchanged and
returns false.
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(25)
Data Structures – CSC212
Operation
Specification
void update(Type)
Precondition/Requires: BT is not empty.
Processing/Results: update the value of data of the current node.
Type retrieve()
Precondition/Requires: BT is not empty.
Processing/Results: returns data of the current node.
void delete_sub()
Precondition: BT is not empty.
Process: the subtree whose root node was the current node before this
operation is deleted from the tree. In case the resulting tree is not empty then
current = root.
Note: Relative is enumerated type and is confined to the values {Root, Parent, LeftChild, RightChild}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(26)
Data Structures – CSC212
Represent ion of Binary Tree ADT
A binary tree can represented using
- Linked List
- Array
Note : Array is suitable only for full and complete
binary trees
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(27)
Data Structures – CSC212
Linked List based Implementation
public class BTNode <T>
{
public T data;
public BTNode<T> left, right;
public BTNode(T val)
{
data = val;
left = right = null;
}
public BTNode(T val, BTNode<T> l, BTNode<T> r)
{
data = val;
left = l;
right = r;
}
}
public enum Order {preOrder, inOrder, postOrder};
Dr Muhammad Hussain
Lecture - Binary Tree ADT
Data Structures – CSC212
(28)
public class BT<T>{
//Data Members
BTNode<T> root, current;
public BT()
// Private Methods
private void preorder(BTNode<T> p)
private void inorder(BTNode<T> p)
private void postorder(BTNode<T> p)
private BTNode<T> findparent (BTNode<T> p) // non-recursive
private BTNode<T> findparent (BTNode<T> p, BTNode<T> t)
// Operations
public void traverse(Order ord)
public boolean empty()
public boolean find (Relative rel)
public boolean insert (Relative rel, T val)
public T retrieve ()
public void update (T val)
public void delete_subtree()
}
public enum Relative {Root, Parent, LeftChild, RightChild};
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(29)
Data Structures – CSC212
Implementation of Private Methods
private void preorder(BTNode<T> p)
{
if (p != null){
System.out.println(p.data);
preorder(p.left);
preorder(p.right);
}
}
private void inorder(BTNode<T> p)
{
if (p != null){
inorder(p.left);
System.out.println(p.data);
inorder(p.right);
}
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(30)
Data Structures – CSC212
Implementation of Private Methods
private void postorder(BTNode<T> p)
{
if (p != null){
postorder(p.left);
postorder(p.right);
System.out.println(p.data);
}
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(31)
Data Structures – CSC212
Implementation of Private Methods
/* Non-recursive version of findparent */
private BTNode<T> findparent (BTNode<T> p)
{
LinkStack<BTNode<T>> stack = new LinkStack<BTNode<T>>();
BTNode<T> q = root;
while (q.right != p && q.left != p){
if (q.right != null) stack.push(q.right);
if (q.left != null)
q = q.left;
else
q = stack.pop();
}
return q;
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(32)
Data Structures – CSC212
Implementation of Private Methods
/* Recursive version of findparent - uses pre-order
traversal */
private BTNode<T> findparent (BTNode<T> p, BTNode<T> t)
{
if (t == null) return null; /* empty tree */
if (t.right == null && t.left == null)
return null;
else if (t.right == p || t.left == p)
return t; /* parent is t */
else {
BTNode q = findparent(p, t.left);
if (q != null)
return q;
else
return findparent(p, t.right);
}
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(33)
Data Structures – CSC212
Implementation of Operations
public BT()
{
root = current = null;
}
public void traverse(Order ord)
{
switch (ord) {
case preOrder: preorder(root);
break;
case inOrder:
inorder(root);
break;
case postOrder: postorder(root);
break;
default:
break;
}
return;
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(34)
Data Structures – CSC212
Implementation of Operations
public boolean find (Relative rel){
switch (rel) {
case Root:
current = root;
return true;
case Parent:
if (current == root) return false;
current = findparent(current, root);
return true;
case LeftChild:
if (current.left == null) return false;
current = current.left;
return true;
case RightChild:
if (current.right == null) return false;
current = current.right;
return true;
default:
return false;
}
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(35)
Data Structures – CSC212
Implementation of Operations
public boolean insert (Relative rel, T val) {
switch (rel) {
case Root:
if (! empty()) return false;
current = root = new BTNode<T>(val);
return true;
case Parent:
return false;
case LeftChild:
if (current.left != null) return false;
current.left = new BTNode<T>(val);
current = current.left;
return true;
case RightChild:
if (current.right != null) return false;
current.right = new BTNode<T> (val);
current = current.right;
return true;
default:
return false;
}
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(36)
Data Structures – CSC212
Implementation of Operations
public T retrieve ()
{
return current.data;
}
public void update (T val)
{
current.data = val;
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(37)
Data Structures – CSC212
Implementation of Operations
public void delete_subtree()
{
if (current == root){
current = root = null;
}
else {
BTNode<T> p = current;
find(Relative.Parent);
if (current.left == p)
current.left = null;
else
current.right = null;
current = root;
}
}
Dr Muhammad Hussain
Lecture - Binary Tree ADT
(38)
Data Structures – CSC212
Height and the number of nodes in a Binary Tree
 If the height of a binary tree is h then the maximum number of nodes in the tree
is 2h -1
 If the number of nodes in a complete binary tree is n, then
2h - 1 = n
2h = n + 1
h = log(n+1)  O(logn)
Dr Muhammad Hussain
Lecture - Binary Tree ADT