A binary tree is "threaded" by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node."
(Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1989, p. 175. ISBN 978-0-201-16116-8.)
A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal.
It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).
This is possible, because if a node (k) has a right child (m) then m's left pointer must be either a child, or a thread back to k. In the case of a left child, that left child must also have a left child or a thread back to k, and so we can follow m's left children until we find a thread, pointing back to k. The situation is similar for when m is the left child of k
In Python:def parent(node): if node is node.tree.root: return None else: x = node y = node while True: if is_thread(y.right): p = y.right if p is None or p.left is not node: p = x while not is_thread(p.left): p = p.left p = p.left return p elif is_thread(x.left): p = x.left if p is None or p.left is not node: p = y while not is_thread(p.right): p = p.right p = p.right return p x = x.left y = y.right
External links
* [http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_bst1.aspx#thread Tutorial on threaded binary trees] * [http://www.stanford.edu/~blp/avl/libavl.html/Threaded-Binary-Search-Trees.html GNU libavl 2.0.2, Section on threaded binary search trees]
Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… … Wikipedia
Tree traversal — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional … Wikipedia
Threaded code — Not to be confused with multi threaded programming. In computer science, the term threaded code refers to a compiler implementation technique where the generated code has a form that essentially consists entirely of calls to subroutines. The code … Wikipedia
List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… … Wikipedia
Список терминов — Список терминов, относящихся к алгоритмам и структурам данных Это сл … Википедия
Radix sort — In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is… … Wikipedia
Persistent data structure — In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in… … Wikipedia
Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… … Wikipedia
Linux kernel — Linux Linux kernel 3.0.0 booting Company / developer Linus Torvalds and thousands … Wikipedia
