Scribd
Upload
250 views18 pages

Threaded Binary Trees

Threaded binary trees utilize unused null pointers in binary trees to perform inorder traversals more efficiently. There are two types of threading - one-way threading uses right pointers only, while two-way threading uses both left and right pointers. During traversal, nodes are printed by following threads to the right or links to the leftmost child, allowing traversal without recursion or stacks.

Uploaded by

Anonymous V7P5fNQI
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
250 views18 pages

Threaded Binary Trees

Threaded binary trees utilize unused null pointers in binary trees to perform inorder traversals more efficiently. There are two types of threading - one-way threading uses right pointers only, while two-way threading uses both left and right pointers. During traversal, nodes are printed by following threads to the right or links to the leftmost child, allowing traversal without recursion or stacks.

Uploaded by

Anonymous V7P5fNQI
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 18

Threaded Binary Trees

Demerits of Binary Trees


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

Need for Threaded Binary Tree


A binary tree with n nodes need 2n pointers out

of which (n+1) are null pointers


A.J. Perlis and C.Thomson devised a method to

utilize these (n+1) null pointers as threads


Threads that take place of a left child pointer

indicate inorder predecessor and right child pointer lead to inorder successor

Definition
Threaded binary tree is the left subtree of a root

node whose right child pointer points to itself.

Data Structures for Threaded BT


left_thread
TRUE

left_child

data

right_child
FALSE

right_th

TRUE: thread

FALSE: child

One Way Threading


Thread appears only on the RLINK of a node,

pointing to the inorder successor of the node

6 3 1 5 7 9 8 11 13

Two Way Threading


Thread appears in both LLINK and RLINK of a

node, pointing to the inorder predecessor and


inorder successor respectively.

6 3 8

7
9

11
13

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


8

Threaded Tree Traversal

6
3 8

Output 1

7
9

11
13

Start at leftmost node, print it


9

Threaded Tree Traversal

6
3 8

Output 1 3

7
9

11
13

Follow thread to right, print node


10

Threaded Tree Traversal

6
3 8

Output 1 3 5

7
9

11
13

Follow link to right, go to leftmost node and print


11

Threaded Tree Traversal

6
3 8

Output 1 3 5 6

7
9

11
13

Follow thread to right, print node


12

Threaded Tree Traversal

6
3 8

7
9

11
13

Output 1 3 5 6 7

Follow link to right, go to leftmost node and print


13

Threaded Tree Traversal

6
3 8

7
9

11
13

Output 1 3 5 6 7 8

Follow thread to right, print node


14

Threaded Tree Traversal

6
3 8

7
9

11
13

Output 1 3 5 6 7 8 9

Follow link to right, go to leftmost node and print


15

Threaded Tree Traversal

6
3 8

7
9

11
13

Output 1 3 5 6 7 8 9 11

Follow thread to right, print node


16

Threaded Tree Traversal

6
3 8

7
9

11
13

Output 1 3 5 6 7 8 9 11 13

Follow link to right, go to leftmost node and print


17

Inorder Traversal of Threaded Binary Tree


void threadedinorder(Root P) { do { if P TRPOINT = = True then P=P RLINK; else P=P RLINK; while(P TLPOINT ! = TRUE) P=P LLINK; if(P!=ROOT) print(p data) }while(P = = ROOT); }

You might also like