Understand Threaded Binary Trees for Efficient Data Storage
Learn about Threaded Binary Trees, a structure that optimizes storage by eliminating unnecessary null pointers, reducing the need for stack and queue storage. Discover the different types of Threaded Binary Trees and their advantages in various traversal methods. Explore how pointers like "Thread" are utilized in Threaded Binary Trees for efficient data representation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
THREADED BINARY THREADED BINARY TREE TREE Presented by : Khushi .S. Desarda. Guided by: Prof: Deepali .P. Pawar.
Why we use Threaded Binary Tree? As we know in Normal Binary As we know in Normal Binary Tree, there are many null Tree, there are many null pointers which do not store any pointers which do not store any value in it. value in it. In Binary Tree , Majority (N+1) In Binary Tree , Majority (N+1) Pointers are Null. Pointers are Null. In Binary Tree , we need a large In Binary Tree , we need a large storage for Stack and Queue. storage for Stack and Queue. So, to avoid this above points, we So, to avoid this above points, we have Threaded binary Tree. have Threaded binary Tree. In Threaded Binary Tree, we In Threaded Binary Tree, we store meaningful information in store meaningful information in these NULL pointers. these NULL pointers. Eliminate the use of stack and Eliminate the use of stack and queue, so that it requires less queue, so that it requires less storage. storage.
DEFINATION In Threaded Binary Tree the special In Threaded Binary Tree the special pointer called Thread is used to pointer called Thread is used to point to nodes of higher value in the point to nodes of higher value in the tree . tree . As in Threaded Binary Tree there As in Threaded Binary Tree there are Three traversal : are Three traversal : Inorder Traversal Inorder Traversal Pre Pre- -Order Traversal Order Traversal Post Order Traversal Post Order Traversal We will see the Concept of We will see the Concept of Threaded Binary Tree in Inorder Threaded Binary Tree in Inorder Traversal. Traversal.
There are Two Types of Threaded Binary Tree 1.One way Threaded Binary Tree In that there are two types : a) Right way threading. b) Left way threading. 2. Double Threaded Binary Tree.
Right Threaded Right Threaded Binary Tree Binary Tree In Right Threaded Binary Tree all Right Null Pointers, points to it s inorder successor. Inorder is : DBFEGAC If Right Pointer has no inorder successor then it points to header node which is above the root node.
Left Threaded Left Threaded Binary Tree Binary Tree In Left Threaded Binary Tree all Left Null Pointers, points to it s inorder predecessor. Inorder is : DBFEGAC. If Left Pointer has no inorder predecessor then it points to a header node which is above root node.
Fully Threaded Fully Threaded Binary Tree Binary Tree In fully Threaded Binary tree all the right pointers points to it s inorder successor and all the left null pointers point to it s inorder predecessor.
Deletion In Threaded Binary Tree Leaf Node to be deleted(Left Child): Deleting node 14 means to delete it directly from the tree and with that all the links and threads connected to 14 will be deleted. Before deleting the node the inorder of TBT is : 5 10 14 16 17 20 30. As 16 will not have left child. After deleting the node the inorder of TBT is : 5 10 16 17 20 30 If the leaf node to be deleted is left child of it s parent then after deletion, left pointer of parent should become a thread pointing to it s predecessor. Now for 16 the predecessor is 10.
Deletion In Threaded Binary Tree Leaf Node to be deleted (Right Child): Deleting node 17 means to delete it directly from the tree and with that all the links and threads connected to 17 will be deleted. Before deleting the node the inorder of TBT is : 5 10 14 16 17 20 30. As 16 will not have right child. After deleting the node the inorder of TBT is : 5 10 14 16 20 30 If the leaf node to be deleted is right child of it s parent then after deletion, right pointer of parent should become a thread pointing to it s successor. Now for 16 the successor is 20.
Deleting a Node Having One Child Deleting node 16 We replace the node 16 with the value of it s child node 14. Before deleting the node 16 the inorder traversal is : 5 10 13 14 15 16 20 30. If node to be deleted has left subtree then after deletion right thread of it s predecessor should point to its successor. After deleting the node 16 the inorder traversal is: 5 10 13 14 15 20 30. Before deletion 15 is predecessor and 20 is successor of 16. After deletion of 16 , the node 20 becomes the successor of 15,so right thread of 15 will point to 20.
