Scribd
Upload
17 views7 pages

APAssignment 9

The document describes the key operations for a threaded binary search tree: 1. Inserting an element involves recursively adding the element to the left or right subtree or linking it as a successor to an empty child pointer. 2. Searching traverses left or right children recursively until the key is found or a threaded child is reached. 3. Deleting removes the node, replaces it if it has two children, and relinks parent and child pointers accordingly. 4. Inorder traversal iterates leftmost first then recursively finds the next node.

Uploaded by

Dharmatej Mallampati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views7 pages

APAssignment 9

The document describes the key operations for a threaded binary search tree: 1. Inserting an element involves recursively adding the element to the left or right subtree or linking it as a successor to an empty child pointer. 2. Searching traverses left or right children recursively until the key is found or a threaded child is reached. 3. Deleting removes the node, replaces it if it has two children, and relinks parent and child pointers accordingly. 4. Inorder traversal iterates leftmost first then recursively finds the next node.

Uploaded by

Dharmatej Mallampati
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment 9

-----------------------------------------------------------------------------------

Q. Implement Threaded Binary Search Tree

The Threaded Binary Search Tree implementations consists of 4


operations. They are as follows:
1. Inserting an element
2. Searching for an element
3. Deleting an element
4. Inorder traversal

ALGORITHM:
Inserting an Element :

if node = NULL
{
Create a new node with value
node -> lthread = 1, node -> rthread = 1
Return new node
else if value <= node's value
{
if node -> lthread = 1
{
Create a new node with value
newnode -> lthread = 1
newnode-> rthread = 1
newnode -> left pointer = current node left child
current node -> left pointer = newnode
current node -> lthread = 0
}
else
{
Recursively insert value into left subtree
}

else if value >= node's value


{
if rthread = 1
{
Create a new node with value
newnode -> lthread = 1
newnode -> rthread = 1
newnode -> right = current node's right child
current node -> right = new node
current node -> rthread = 0
}
else
{
Recursively insert value into right subtree
}
}
Return modified node

Searching for an element:

current = root
while current is not null
{
if key = current->info
{
return current
}
else if key < current -> info
{
if current -> lthread = 0
{
current = current->left
}
else
{
break
}
}
else
{
if current -> rthread = 0:
current = current -> right
else
break
}
return null

Deleting an element:

if rootNode is null
{
return null
}
parent = null
current = rootNode

while current != null && current != nodeToDelete


{
parent = current
if nodeToDelete->value < current->value
{
if current -> lthread = 0
{
current = current -> left
}
else
{
break
}
else
{
if current->rthread = 0
{
current = current->right
}
else
{
break
}
}

if current = null
{
return rootNode
}

if current -> lthread = 0 && current -> rthread = 0


{
successor = findInOrderSuccessor(current)
current->value = successor->value
}

if current->lthread = 0
{
if parent = null
{
rootNode = current->left
}
else if parent->left = current
{
Parent-> left = current-> left
}
else
{
parent-> right = current-> left
}

else if current-> rthread = 0


{
if parent = null
{
rootNode = current-> right
}
else if parent->left = current
{
parent->left = current->right
}
else
{
parent->right = current->right
}
}
else
{
if parent = null
{
rootNode = null
}
else if parent->left = current
{
parent->lthread = 1
parent->left = [Link]
}

else
{
parent->rthread = 1
parent->right = current->right
}
}
free(current)
return rootNode

Inorder Traversal:

if root = null
{
print "Tree is empty”
}
else
{
current = leftmost(root)
while current is not null
{
print current-> info
current = inorderSuccessor(current)
}
}

function leftmost(node) :
while node -> lthread = false
{
node = node -> left
}
return node
function inorderSuccessor(node) :
if node -> rthread
{
return node -> right
}
node = node -> right
while node -> lthread is false
{
node = nodeleft
}
return node

You might also like