In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right.... may be defined as follows:
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.
Discussion
Ask a question about 'Threaded binary tree'
Start a new discussion about 'Threaded binary tree'
In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right.... may be defined as follows:
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.)
In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right.... makes it possible to traverse the values in the binary tree
Binary tree
In computer science, a binary tree is a Tree in which each node has at most two child node. Typically the child nodes are called left and right.... 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
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree data structure, tree structure, or graph . One starts at the root and explores as far as possible along each branch before backtracking.... ).
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
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are Minimalism , while the standard library is large and comprehensive.... :
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
