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 bourgeoisie loves so-called “positive” types and novels with happy endings since they lull one into thinking that it is fine to simultaneously acquire capital and maintain one’s innocence, to be a beast and still be happy.”
    —Anton Pavlovich Chekhov (1860–1904)

    “For many are the trees of God that grow
    In Paradise, and various, yet unknown
    To us; in such abundance lies our choice
    As leaves a greater store of fruit untouched,
    Still hanging incorruptible, till men
    Grow up to their provision, and more hands
    Help to disburden Nature of her bearth.””
    —John Milton (1608–1674)