Downloaded 885 times
Uploaded bykhabbab_h
Threaded Binary Tree
The document discusses threaded binary trees, which optimize the use of null pointers by replacing them with threads that point to in-order predecessors and successors. It outlines the structure, advantages, and disadvantages of threaded binary trees compared to normal binary trees, highlighting efficient memory usage and traversal but noting complexities in insertion and deletion. The presentation also includes traversal algorithms and examples for better understanding of threaded binary trees.
In this document
Powered by AI
Introduction to the presentation and its presenters.
Definition of a threaded binary tree, utilizes null pointers for in-order predecessor and successor.Details on null pointers in a binary tree, generalizations about pointer structure.
Description of one-way threaded trees using in-order successors.
Explanation of two-way threading and its structure.
Approach to solve dangling pointers using a header node.
Node structure of threaded binary trees defined for this study.
Traversal process details in a threaded binary tree, including outputs.
Comparison of threaded binary trees with normal binary trees with pros and cons.
Procedure for inserting nodes into a threaded binary tree with examples.
Advantages of reduced memory use and improved traversal, versus complexity.
General applications of threaded binary trees in computing.
Final thoughts on the benefits and limitations of threaded binary trees.
List of sources for further reading and reference materials.
Contact information for inquiries related to the presentation.
Threaded Binary Tree
- 1. Presented to: Md. Shamsujjoha Senior Lecturer of CSE department East West University Presented by: Md. Khabbab Hossain Tusher Date:03/04/2016
- 2.
- 3. A binary searchtree in which each node uses an otherwise-empty left child link to refer to the node's in-order predecessor and an empty right child link to refer to its in-Order Successor. Definition Slide 1
- 4. A Simple BinaryTree A B D E C GF Slide 2
- 5. A B C Null DNull Null E Null Null G NullNull F Null Slide 3 Threaded binary tree
- 6. Threaded Binary Tree In above binary tree, there are 8 null pointers & actual 6 pointers. In all there are 14 pointers. We can generalize it that for any binary tree with n nodes there will be (n+1) null pointers and 2n total pointers. The objective here to make effective use of these null pointers. A. J. perils & C. Thornton jointly proposed idea to make effective use of these null pointers. According to this idea we are going to replace all the null pointers by the appropriate pointer values called threads. Slide 4
- 7. And binarytree with such pointers are called threaded tree. In the memory representation of a threaded binary tree, it is necessary to distinguish between a normal pointer and a thread. Slide 5
- 8. Threaded Binary Tree: One-Way We will use the right thread only in this case. To implement threads we need to use in-order successor of the tree Slide 6
- 9. Threaded Binary Tree: One-Way A BC Null D Null E Null G NullNull F Inorder Traversal of The tree: D, B, E, A, F, C, G Slide 7
- 10. Two way ThreadedTree/Double Threads Again two-way threading has left pointer of the first node and right pointer of the last node will contain the null value. The header nodes is called two-way threading with header node threaded binary tree. Slide 8
- 11. A B D Inorder Traversal ofThe tree: D, B, E, A, F, C, G E C F G Dangling Dangling Slide 9
- 12. • Dangling canbe solved as follows Introduce a header node. The left and right pointer of the header node are treated as normal links and are initialized to point to header node itself. Slide 10
- 13. A B D Inorder Traversal ofThe tree: D, B, E, A, F, C, G E C F G Head Slide 11
- 14. Structure of ThreadBT Node structure For the purpose of our evaluation algorithm, we assume each node has five fields: LTag Left data Right RTag We define this node structure in C as: Struct Node{ int data; struct Node *Left,*Right; bool Ltag; boolRtag; }; Slide 12
- 15. L.Tag L.Child headR.child R.Tag 1 A 1 1 1 0 D 0 0 E 0 0 F 0 0 G 0 1 B 1 1 C 1 Inorder Traversal of The tree: D B E A F C G Slide 13
- 16. 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. Slide 14
- 17. 8 75 3 1 6 Start at leftmostnode, print it Output 1 9 Slide 15
- 18. 8 75 3 1 6 Follow thread toright, print node Output 1 3 9 Slide 16
- 19. 8 75 3 1 6 Follow link toright, go to leftmost node and print Output 1 3 5 9 Slide 17
- 20. 8 75 3 1 6 Follow thread toright, print node Output 1 3 5 6 9 Slide 18
- 21. 8 75 3 1 6 Follow link toright, go to leftmost node and print Output 1 3 5 6 7 9 Slide 19
- 22. 8 75 3 1 6 9 Follow thread toright, print node Output 1 3 5 6 7 8 Slide 20
- 23. 8 75 3 91 6 Follow link toright, go to leftmost node and print Output 1 3 5 6 7 8 9 Slide 21
- 24. void inOrder(struct Node*root) { struct Node *cur = leftmost(root); while (cur != NULL) { printf("%d ", cur->data); // If this node is a thread node, then go to // inorder successor if (cur->rightThread) cur = cur->right; else // Else go to the leftmost child in right subtree cur = leftmost(cur->right); } } 8 75 3 1 6 9 Slide 22
- 25. Threaded Binary Trees In threaded binary trees, The null pointers are used as thread. We can use the null pointers which is a efficient way to use computers memory. Traversal is easy. Completed without using stack or reccursive function. Structure is complex. Insertion and deletion takes more time. Normal Binary Trees In a normal binary trees, the null pointers remains null. We can’t use null pointers so it is a wastage of memory. Traverse is not easy and not memory efficient. Less complex than Threaded binary tree. Less Time consuming than Threaded Binary tree. Comparison of Threaded BT Slide 23
- 26. Inserting anode to Threaded Binary Tree: Inserting a node X as the right child of a nodes. 1st Case: - If G has an empty right subtree, then the insertion is simple Slide 24
- 27. A B D Inserting X asa right child of G E C F G Head X New inorder traversal is: D,B,E,A,F,C,G,X Slide 25
- 28. 2nd Case: If theright subtree of C is not empty, then this right child is made the right child of X after insertion. Slide 26
- 29. A B D New Inorder Traversalof The tree: D, B, E, A, F, C, X,G E F G Head x C Slide 27
- 30. Advantage 1. Bydoing threading we avoid the recursive method of traversing a Tree , which doesn’t use of stack and consumes a lot of memory and time . 2 . The node can keep record of its root . 3. Backward Traverse is possible. 4. Applicable in most types of the binary tree. Disadvantage 1. This makes the Tree more complex . 2. More prone to errors when both the child are not present & both values of nodes pointer to their ancestors. 3. Lot of time consumes when deletion or insertion is performed. Threaded binary tree Slide 28
- 31. Same asany kind of Binary Tree. Used in search and Traverse based work APPLICATIONS Slide 29
- 32. Conclusion Excellent conceptin modern computer science. Saves Time and memory. Traversal and search are very efficient. Insertion and deletion are not so efficient. Slide 30
- 33. References http://www.geeksforgeeks.org/inorder-tree-traversal-without- recursion-and-without-stack/ http://www.delorie.com/gnu/docs/avl/libavl_183.html http://www.math- cs.gordon.edu/courses/cs321/lectures/threaded.html https://prezi.com/1yitau0wnwlg/threaded-binary-tree-in-data- structures/ http://stackoverflow.com/questions/6744770/confusion-with- threaded-binary-tree Various Text Book for data structure.
- 35.