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 types his laboured column—weary drudge!
    Senile fudge and solemn:
    Spare, editor, to condemn
    These dry leaves of his autumn.”
    —Robertson Davies (b. 1913)

    “Usually the scenery about them is drear and savage enough; and the logger’s camp is as completely in the woods as a fungus at the foot of a pine in a swamp; no outlook but to the sky overhead; no more clearing than is made by cutting down the trees of which it is built, and those which are necessary for fuel.”
    —Henry David Thoreau (1817–1862)