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)

    “He’s one of those know-it-all types that, if you flatter the wig off him, he chatter like a goony bird at mating time.”
    —Michael Blankfort. Lewis Milestone. Johnson (Reginald Gardner)

    “A long war like this makes you realise the society you really prefer, the home, goats chickens and dogs and casual acquaintances. I find myself not caring at all for gardens flowers or vegetables cats cows and rabbits, one gets tired of trees vines and hills, but houses, goats chickens dogs and casual acquaintances never pall.”
    —Gertrude Stein (1874–1946)