Threaded Binary Tree - Types of Binary Trees

Types of Binary Trees

  1. Single Threaded: each node is threaded towards either the inorder predecessor or successor.
  2. Double threaded: each node is threaded towards both the inorder predecessor and successor.

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.right 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

Read more about this topic:  Threaded Binary Tree

Famous quotes containing the words types of and/or types:

    “Science is intimately integrated with the whole social structure and cultural tradition. They mutually support one other—only in certain types of society can science flourish, and conversely without a continuous and healthy development and application of science such a society cannot function properly.”
    —Talcott Parsons (1902–1979)

    “If there is nothing new on the earth, still the traveler always has a resource in the skies. They are constantly turning a new page to view. The wind sets the types on this blue ground, and the inquiring may always read a new truth there.”
    —Henry David Thoreau (1817–1862)