Scribd Logo
Upload

Welcome to Scribd!

  • 64 views

    Travesal Methods

    Uploaded by

    Odirile Masogo
    Binary tree traversal methods include preorder, inorder, postorder, and level order traversal. Preorder visits the root node first, then left subtree, then right subtree. Inorder visits left subtree, then root, then right subtree. Postorder visits left subtree, right subtree, then root node. Level order traversal visits nodes level by level from left to right. Given inorder and preorder traversals, the binary tree can be uniquely reconstructed.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Travesal Methods

    Uploaded by

    Odirile Masogo
    64 views14 pages
    Binary tree traversal methods include preorder, inorder, postorder, and level order traversal. Preorder visits the root node first, then left subtree, then right subtree. Inorder visits left subtree, then root, then right subtree. Postorder visits left subtree, right subtree, then root node. Level order traversal visits nodes level by level from left to right. Given inorder and preorder traversals, the binary tree can be uniquely reconstructed.

    Original Description:

    Finance Amity

    Original Title

    Travesal methods;

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Binary tree traversal methods include preorder, inorder, postorder, and level order traversal. Preorder visits the root node first, then left subtree, then right subtree. Inorder visits left subtree, then root, then right subtree. Postorder visits left subtree, right subtree, then root node. Level order traversal visits nodes level by level from left to right. Given inorder and preorder traversals, the binary tree can be uniquely reconstructed.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    64 views14 pages

    Travesal Methods

    Uploaded by

    Odirile Masogo
    Binary tree traversal methods include preorder, inorder, postorder, and level order traversal. Preorder visits the root node first, then left subtree, then right subtree. Inorder visits left subtree, then root, then right subtree. Postorder visits left subtree, right subtree, then root node. Level order traversal visits nodes level by level from left to right. Given inorder and preorder traversals, the binary tree can be uniquely reconstructed.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 14

    Binary Tree Traversal Methods

    • In a traversal of a binary tree, each element of


    the binary tree is visited exactly once.
    • During the visit of an element, all action (make
    a clone, display, evaluate the operator, etc.)
    with respect to this element is taken.

    Binary Tree Traversal Methods

    • Preorder
    • Inorder
    • Postorder
    • Level order
    Preorder Traversal
    public static void preOrder(BinaryTreeNode t)
    {
    if (t != null)
    {
    visit(t);
    preOrder(t.leftChild);
    preOrder(t.rightChild);
    }
    }

    Preorder Example (visit = print)


    a

    b c

    abc
    Preorder Example (visit = print)
    a

    b c
    f
    d e
    g h i j

    abdghei cf j

    Preorder Of Expression Tree


    /

    * +
    e f
    + -
    a b c d

    / * +a b - c d +e f

    Gives prefix form of expression!


    Inorder Traversal
    public static void inOrder(BinaryTreeNode t)
    {
    if (t != null)
    {
    inOrder(t.leftChild);
    visit(t);
    inOrder(t.rightChild);
    }
    }

    Inorder Example (visit = print)


    a

    b c

    bac
    Inorder Example (visit = print)
    a

    b c
    f
    d e
    g h i j

    gdhbei af j c

    Inorder By Projection (Squishing)


    a

    b c
    f
    d e
    g h i j

    g d h b e i a f jc
    Inorder Of Expression Tree
    /

    * +
    e f
    + -
    a b c d

    a + b * c - d/ e + f

    Gives infix form of expression (sans parentheses)!

    Postorder Traversal
    public static void postOrder(BinaryTreeNode t)
    {
    if (t != null)
    {
    postOrder(t.leftChild);
    postOrder(t.rightChild);
    visit(t);
    }
    }
    Postorder Example (visit = print)
    a

    b c

    bca

    Postorder Example (visit = print)


    a

    b c
    f
    d e
    g h i j

    ghdi ebj f ca
    Postorder Of Expression Tree
    /

    * +
    e f
    + -
    a b c d

    a b +c d - * e f + /

    Gives postfix form of expression!

    Traversal Applications
    a

    b c
    f
    d e
    g h i j

    • Make a clone.
    • Determine height.
    •Determine number of nodes.
    Level Order

    Let t be the tree root.


    while (t != null)
    {
    visit t and put its children on a FIFO queue;
    remove a node from the FIFO queue and
    call it t;
    // remove returns null when queue is empty
    }

    Level-Order Example (visit = print)


    a

    b c
    f
    d e
    g h i j

    abcdef ghi j
    Binary Tree Construction
    • Suppose that the elements in a binary tree
    are distinct.
    • Can you construct the binary tree from
    which a given traversal sequence came?
    • When a traversal sequence has more than
    one element, the binary tree is not uniquely
    defined.
    • Therefore, the tree from which the sequence
    was obtained cannot be reconstructed
    uniquely.

    Some Examples
    preorder a a
    = ab b b

    inorder b a
    = ab a b

    postorder b b
    = ab a a

    level order a a
    = ab b b
    Binary Tree Construction

    • Can you construct the binary tree,


    given two traversal sequences?
    • Depends on which two sequences are
    given.

    Preorder And Postorder

    preorder = ab a a
    postorder = ba b b

    • Preorder and postorder do not uniquely define a


    binary tree.
    • Nor do preorder and level order (same example).
    • Nor do postorder and level order (same example).
    Inorder And Preorder
    • inorder = g d h b e i a f j c
    • preorder = a b d g h e i c f j
    • Scan the preorder left to right using the
    inorder to separate left and right subtrees.
    • a is the root of the tree; gdhbei are in the left
    subtree; fjc are in the right subtree.
    a

    gdhbei fjc

    Inorder And Preorder


    a

    gdhbei fjc

    • preorder = a b d g h e i c f j
    • b is the next root; gdh are in the left
    subtree; ei are in the right subtree.
    a

    b fjc
    gdh ei
    Inorder And Preorder
    a

    b fjc
    gdh ei
    • preorder = a b d g h e i c f j
    • d is the next root; g is in the left
    subtree; h is in the right subtree.
    a
    b fjc
    d ei
    g h

    Inorder And Postorder

    • Scan postorder from right to left using


    inorder to separate left and right subtrees.
    • inorder = g d h b e i a f j c
    • postorder = g h d i e b j f c a
    • Tree root is a; gdhbei are in left subtree; fjc
    are in right subtree.
    Inorder And Level Order

    • Scan level order from left to right using


    inorder to separate left and right subtrees.
    • inorder = g d h b e i a f j c
    • level order = a b c d e f g h i j
    • Tree root is a; gdhbei are in left subtree; fjc
    are in right subtree.

    You might also like