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)

    “The nectar and ambrosia, are withheld;
    And in the midst of spoils and slaves, we thieves
    And pirates of the universe, shut out
    Daily to a more thin and outward rind,
    Turn pale and starve. Therefore, to our sick eyes,
    The stunted trees look sick, the summer short,
    Clouds shade the sun, which will not tan our hay,
    And nothing thrives to reach its natural term;”
    —Ralph Waldo Emerson (1803–1882)