Transcript Binary Trees

Binary Trees and
Binary Search Trees
Based on Dale & Co: Object-Oriented Data Structures using C++ (graphics)
1
Binary Tree
A binary tree is a structure in which:
Each node can have at most two children,
and in which a unique path exists from
the root to every other node.
The two children of a node are called the
left child and the right child, if they exist.
2
A Binary Tree
V
Q
L
T
E
K
A
S
3
How many leaf nodes?
V
Q
L
T
E
K
A
S
4
How many descendants of Q?
V
Q
L
T
E
K
A
S
5
How many ancestors of K?
V
Q
L
T
E
K
A
S
6
A Binary Tree with Tree Nodes
V
Q
L
T
E
K
A
S
7
Node Terminology for a Tree Node
8
Binary Trees

You can write a class that represents each
node in a binary tree


Called BinaryTreeNode
Instance variables of the class
BinaryTreeNode
info: stores the information part of the node
 lLink: points to the root node of the left subtree
 rLink: points to the root node of the right subtree

9
Tree Traversals
Insertion, deletion, and lookup (and
other) operations require that the binary
tree be traversed
 Commonly used traversals

 Inorder
traversal
 Preorder traversal
 Postorder traversal
10
Tree Traversals: In Order Print
11
Inorder (tree): LeftNodeRight

Binary tree is traversed as follows:

Traverse left subtree
 Visit node
 Traverse right subtree
private void inorder(BinaryTreeNode<T> t){
if (t != null)
{
inorder(t.lLink);
System.out.print(t.info + “ “);
inorder(t.rLink);
}
}
To print in alphabetical order
12
Postorder (tree): LeftRightNode

Binary tree is traversed as follows:

Traverse left subtree
 Traverse right subtree
 Visit node
private void postorder(BinaryTreeNode<T> t){
if (t != null){
postorder(t.lLink);
postorder(t.rLink);
System.out.print(t.info + “ “);
}
}
Visits leaves first (good for deletion)
13
Preorder (tree): NodeLeftRight

Binary tree is traversed as follows:
 Visit node
 Traverse left subtree
 Traverse right subtree
private void preorder(BinaryTreeNode<T> t){
if (t != null) {
System.out.print(t.info + “ “);
preorder(t.lLink);
preorder(t.rLink);
}
}
Useful with binary trees (not BST)
14
Three Tree Traversals
15
Binary Search Trees (BST)

To search for an item in a normal binary tree,
you must traverse entire tree until item is
found



Search process will be very slow
Similar to searching in an arbitrary linked list
Binary search tree

Data in each node is
– Larger than the data in its left child
– Smaller than the data in its right child
16
So, a Binary Search Tree (BST) is . . .
A special kind of binary tree in which:
1. Each node contains a distinct data value,
2. The key values in the tree can be compared using
“greater than” and “less than”, and
3. The key value of each node in the tree is
less than every key value in its right subtree, and
greater than every key value in its left subtree.
17
The shape of a binary search tree . . .
Depends on its key values and their order of insertion.
Insert the elements ‘J’ ‘E’ ‘F’ ‘T’ ‘A’
in that order.
The first value to be inserted is put into the root node.
‘J’
18
Inserting ‘E’ into the BST
Thereafter, each value to be inserted begins by
comparing itself to the value in the root node,
moving left it is less, or moving right if it is greater.
This continues at each level until it can be inserted
as a new leaf.
‘J’
‘E’
19
Inserting ‘F’ into the BST
Begin by comparing ‘F’ to the value in the root node,
moving left it is less, or moving right if it is greater.
This continues until it can be inserted as a leaf.
‘J’
‘E’
‘F’
20
Inserting ‘T’ into the BST
Begin by comparing ‘T’ to the value in the root node,
moving left it is less, or moving right if it is greater.
This continues until it can be inserted as a leaf.
‘J’
‘T’
‘E’
‘F’
21
Inserting ‘A’ into the BST
Begin by comparing ‘A’ to the value in the root node,
moving left it is less, or moving right if it is greater.
This continues until it can be inserted as a leaf.
‘J’
‘T’
‘E’
‘A’
‘F’
22
What binary search tree . . .
is obtained by inserting
the elements ‘A’ ‘E’ ‘F’ ‘J’ ‘T’
in that order?
‘A’
23
Binary search tree . . .
obtained by inserting
the elements ‘A’ ‘E’ ‘F’ ‘J’ ‘T’
in that order.
‘A’
‘E’
‘F’
‘J’
‘T’
24
Another binary search tree
‘J’
‘T’
‘E’
‘A’
‘H’
‘M’
‘P’
‘K’
Add nodes containing these values in this order:
‘D’
‘B’
‘L’
‘Q’
‘S’
‘V’
‘Z’
25
Is ‘F’ in the binary search tree?
‘J’
‘T’
‘E’
‘A’
‘D’
‘B’
‘V’
‘M’
‘H’
‘Z’
‘P’
‘K’
‘L’
‘Q’
‘S’
26
Tree Recursion
Method countNodes (pseudocode):
if tree is null
return 0
else
return countNodes(Left(tree)) +
countNodes(Right(tree)) + 1
27
The Search Operation
28
The Search Operation
public boolean search(T item) {
return recSearch(root, item);
}
//helper: recursive method called by search
public boolean recSearch(BinaryTreeNode<T> tree, T item) {
if(tree == null)
return false;
else {
Comparable<T> temp = (Comparable<T>) tree.info;
if (temp.compareTo(item) == 0)
return true;
else if (temp.compareTo(item) > 0)
return recSearch(tree.lLink, item);
else
return recSearch(tree.rLink, item);
}
}
29
The Insert Operation

Important: A new node is always
inserted into its appropriate position in
the binary search tree as a leaf.
30
Insertions into a Binary Search Tree
31
The Insert Operation
public void insert(T item) {
root = recInsert(root, item);
}
//helper: recursive method called by insert
public BinaryTreeNode<T> recInsert(BinaryTreeNode<T> tree, T item) {
if(tree == null) {
//create new node
tree = new BinaryTreeNode<T>(item);
}
else {
Comparable<T> temp = (Comparable<T>) tree.info;
if (temp.compareTo(item) == 0) {
System.err.print("Already in - no duplicates.");
return null;
}
else if (temp.compareTo(item) > 0)
tree.lLink = recInsert(tree.lLink, item);
else
tree.rLink = recInsert(tree.rLink, item);
}
return tree;
32
}
The Delete Operation

The delete operation has 3 cases
 Node
to be deleted is a leaf
 Node to be deleted has 1 child (left OR
right)
 Node to be deleted has 2 children
(nonempty left and right subtrees)
33
Deleting a Leaf Node
34
Deleting a Node with One Child
35
Deleting a Node with Two Children (Q)
36
The Delete Operation
Base Case:
If item's key matches Info(tree),
delete node
General Case:
If item < Info(tree),
delete(Left(tree), item);
else
delete(Right(tree), item).
37
Code for Recursive Delete
public void delete(T item) {
root = recDelete(root, item);
}
//helper: recursive method called by delete
public BinaryTreeNode<T> recDelete(BinaryTreeNode<T> tree, T item) {
if(tree == null){
//empty tree
System.err.println("Cannot delete from an empty tree.");
return null;
}
else {
Comparable<T> temp = (Comparable<T>) tree.info;
if (temp.compareTo(item) > 0)
tree.lLink = recDelete(tree.lLink, item);
else if(temp.compareTo(item) < 0)
tree.rLink = recDelete(tree.rLink, item);
else if(tree.lLink != null && tree.rLink != null) {// 2 children
tree.info = findMin(tree.rLink).info;
//tree.info = findMax(tree.lLink).info;
tree.rLink = removeMin(tree.rLink);
}
else if(root.lLink != null) //1 left child
tree = tree.lLink;
else if(root.rLink != null) //1 right child
tree = tree.rLink;
return tree;
}
}
38
Code for Recursive Delete
//helper: method called by recDelete
protected BinaryTreeNode<T> findMin(BinaryTreeNode<T> tree) {
if(tree != null)
while(tree.lLink != null)
tree = tree.lLink;
return tree;
}
//helper: method called by recDelete
protected BinaryTreeNode<T> removeMin(BinaryTreeNode<T> tree) {
if(tree == null){
//empty tree
System.err.println("Cannot delete from an empty tree.");
return null;
}
else if(tree.lLink != null) {
tree.lLink = removeMin(tree.lLink);
return tree;
}
else
return tree.rLink;
39
}