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, types and/or trees:

    “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)

    “The wider the range of possibilities we offer children, the more intense will be their motivations and the richer their experiences. We must widen the range of topics and goals, the types of situations we offer and their degree of structure, the kinds and combinations of resources and materials, and the possible interactions with things, peers, and adults.”
    —Loris Malaguzzi (1920–1994)

    “The trees that have it in their pent-up buds
    To darken nature and be summer woods—”
    —Robert Frost (1874–1963)