UNIT II PART 3

Threaded Binary Tree

THREADED BINARY TREE
 Two many null pointers in current
representation of binary trees
n: number of nodes
number of non-null links: n-1
total links: 2n
null links: 2n-(n-1)=n+1
 Replace these null pointers with some useful

“threads”.
THREADED BINARY TREE
• Binary trees have a lot of wasted space: the
leaf nodes each have 2 null pointers
• We can use these pointers to help us in
inorder traversals
• We have the pointers reference the next
node in an inorder traversal; called threads
• We need to know if a pointer is an actual link
or a thread, so we keep a boolean for each
pointer
THREADED TREE TRAVERSAL
 We start at the leftmost node in the tree,
print it, and follow its right thread
 If we follow a thread to the right, we output

the node and continue to its right

 If we follow a link to the right, we go to the

leftmost node, print it, and continue

THREADED TREE TRAVERSAL
Output
6 1

3 8
1 5 7 11

9 13
Start at leftmost node, print it
THREADED TREE TRAVERSAL
Output
6 1
3

3 8
1 5 7 11

9 13

Follow thread to right, print node

THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5

1 5 7 11

9 13
Follow link to right, go to
leftmost node and print
THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5
6

1 5 7 11

9 13

Follow thread to right, print node

THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5
6
7
1 5 7 11

9 13
Follow link to right, go to
leftmost node and print
THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5
6
7
1 5 7 11 8

9 13

Follow thread to right, print node

THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5
6
7
1 5 7 11 8
9

9 13
Follow link to right, go to
leftmost node and print
THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5
6
7
1 5 7 11 8
9
11
9 13

Follow thread to right, print node

THREADED TREE TRAVERSAL
Output
6 1
3

3 8 5
6
7
1 5 7 11 8
9
11
9 13 13

Follow link to right, go to

leftmost node and print
THREADED TREE MODIFICATION
 We’re still wasting pointers, since half of our
leafs’ pointers are still null
 We can add threads to the previous node in

an inorder traversal as well, which we can

use to traverse the tree backwards or even to
do postorder traversals

14
THREADED TREE MODIFICATION

6
3 8
1 5 7 11

9 13

15
THREADED TREE TRAVERSAL CODE
Node leftMost(Node n) void inOrder(Node n) {
{ Node cur = leftmost(n);
Node ans = n; while (cur != null) {
if (ans == null) { print(cur);
return null; if (cur.rightThread) {
} cur = cur.right;
while (ans.left != } else {
cur =
null) {
leftmost(cur.right);
ans = ans.left; }
} }
return ans; }
}
THREADED BINARY TREES (CONTINUED)

If ptr->left_child is null,
replace it with a pointer to the node that would be
visited before ptr in an inorder traversal

If ptr->right_child is null,
replace it with a pointer to the node that would be
visited after ptr in an inorder traversal
A Threaded Binary Tree
root A
dangling
B C

dangling D E F G

inorder traversal:
H I H, D, I, B, E, A, F, C, G
Data Structures for Threaded
BT
left_thread left_child data right_child right_thread
TRUE   FALSE

TRUE: thread FALSE: child

Class threaded_treenode {
boolean left_thread;
threaded_treenode* left_child;
char data;
threaded_treenode* right_child;
boolean right_thread; };
Memory Representation of A Threaded BT

root --
f f

f A f

f B f f C f

f D f t E t t F t t G t

t H t t I t
Inorder Traversal of Threaded BT
void tinorder(threaded_pointer temp)
{ while(temp!=dummy)
{ while(!temp->left_thread)
temp=temp->left
cout<<temp->data
while(temp->right_thread)
{temp=temp-> right
if(temp==dummy) return;
cout<<temp->data
}
temp=temp-> right
}
}
}
Inserting Nodes into Threaded BTs
 Insert child as the right child of node parent
change parent->right_thread to FALSE
set child->left_thread and
child->right_thread to TRUE
set child->left_child to point to parent
set child->right_child to
parent->right_child
change parent->right_child to point to child
22
Examples
Insert a node D as a right child of B.
root root

A A
(1)
parent
B parent B
(3)
child child
C D C D
(2)
empty
(3)

(2) (1)

(4)

nonempty

Insertion of child as a right child of parent in a threaded binary tree

Right Insertion in Threaded BTs
void insert_right(threaded_pointer parent,
threaded_pointer child)
{
threaded_pointer temp;
child->right_child = parent->right_child;
child->right_thread = parent-
>right_thread;
child->left_child = parent; case (a)
child->left_thread = TRUE;
parent->right_child = child;
parent->right_thread = FALSE;
if (!child->right_thread) { case (b)
temp = insucc(child);
temp->left_child = child;
}
}
CONVERT GIVEN BINARY TREE INTO
THREADED BINARY TREE
 We first do an inorder traversal of the tree and
store it in a queue so that the inorder successor
becomes the next node. We again do an inorder
traversal and whenever we find a node whose
right is NULL, we take the front item from queue
and make it the right of current node. We also set
isThreaded to true to indicate that the right
pointer is a threaded link
 whenever we find a node whose left is NULL, we

take the previous item from queue and make it

the left of current node. We also set isThreaded
to true to indicate that the left pointer is a
threaded link
 .
CASE STUDY: USE OF BINARY TREE IN
EXPRESSION TREE-EVALUATION AND
HUFFMAN'S CODING
 3 + ((5+9)*2)
EVALUATING THE EXPRESSION
REPRESENTED BY EXPRESSION
TREE

Let t be the expression tree

If t is not null then
If t.value is operand then
Return t.value
A = solve(t.left)
B = solve(t.right)

// calculate applies operator

't.value'
// on A and B, and returns value
Return calculate(A, B, t.value)
HUFFMAN CODE
 Very often used for text compression
 Do you know how gzip or winzip works?
  Compression methods

 ASCII code uses codes of equal length for all

letters  how many codes?
 Today’s alternative to ASCII?

 Idea behind Huffman code: use shorter

length codes for letters that are more
frequent
THE BASIC ALGORITHM
 Huffman coding is a form of statistical coding
 Not all characters occur with the same

frequency!
 Yet all characters are allocated the same

amount of space

1 char = 1 byte, be it e or x
THE BASIC ALGORITHM
 Scan text to be compressed and tally occurrence
of all characters.

 Sort or prioritize characters based on number of

occurrences in text.

 Build Huffman code tree based on prioritized list.

 Perform a traversal of tree to determine all code

words.

 Scan text again and create new file using the

Huffman codes.
 http://people.cs.pitt.edu/~kirk/cs1501/animations/
Huffman.html

 Suppose we have given following set of

frequencies
 a-1, b-2, c-3,d-4,e-5,f-6,g-7,h-8
HUFFMAN CODE GENERATION
 To generate a huffman code you traverse the tree
from root to the value you want, outputing
a 0 every time you take a lefthand branch, and
a 1 every time you take a righthand branch.
 Decoding a huffman encoding is just as easy : as

you read bits in from your input stream you

traverse the tree beginning at the root, taking the
left hand path if you read a 0 and the right hand
path if you read a 1. When you hit a leaf, you
have found the code.
ONE MORE EXAMPLE
 character Frequency
 a 5
 b 9
 c 12
 d 13
 e 16
 f 45
 character code-word
 f 0
 c 100
 d 101
 a 1100
 b 1101
 e 111
 Decode this string

 1101111100101111001
struct node
{
char data;
int freq;
node *left, *right;
node(char data, int freq)
{
left = right = NULL;
this->data = data;
this->freq = freq;
}
};

struct compare
{
bool operator()(node* l, node* r)
{
return (l->freq > r->freq);
}
};
void HuffmanCodes(char data[], int freq[], int size)
{
struct node *left, *right, *top;
priority_queue<node*, vector<node*>, compare>
minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new node(data[i], freq[i]));
while (minHeap.size() != 1) {
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
top = new node('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
printCodes(minHeap.top(), "");
}
void printCodes(struct node* root, string str)
{
if (!root)
return;
if (root->data != '$')
cout << root->data << ": " << str << "\n";
printCodes(root->left, str + "0");
printCodes(root->right, str + "1");
}

int main()
{char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 10, 5, 14, 14, 7, 9 };
cout<<"The Character and its Frequency:- "<<endl;
int size = sizeof(arr) / sizeof(arr[0]);
for(int i=0;i<sizeof(arr);i++)
{
cout<<"\t"<<arr[i]<<"\t"<<freq[i]<<endl;
}
cout<<"The Huffman Codes:- "<<endl;
HuffmanCodes(arr, freq, size);
return 0;
}