Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Tree 2

    Uploaded by

    PK Tuber05
    The document discusses different types of binary trees including binary search trees. It defines binary trees, strict binary trees, complete binary trees, extended binary trees, and expression trees. It also covers binary tree representations using arrays and linked lists. Finally, it discusses tree traversals including in-order, pre-order and post-order traversals and provides algorithms to perform each type of traversal. It also describes how to construct and evaluate expression trees representing mathematical expressions.

    Copyright:

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

    Tree 2

    Uploaded by

    PK Tuber05
    28 views19 pages
    The document discusses different types of binary trees including binary search trees. It defines binary trees, strict binary trees, complete binary trees, extended binary trees, and expression trees. It also covers binary tree representations using arrays and linked lists. Finally, it discusses tree traversals including in-order, pre-order and post-order traversals and provides algorithms to perform each type of traversal. It also describes how to construct and evaluate expression trees representing mathematical expressions.

    Original Title

    tree 2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses different types of binary trees including binary search trees. It defines binary trees, strict binary trees, complete binary trees, extended binary trees, and expression trees. It also covers binary tree representations using arrays and linked lists. Finally, it discusses tree traversals including in-order, pre-order and post-order traversals and provides algorithms to perform each type of traversal. It also describes how to construct and evaluate expression trees representing mathematical expressions.

    Copyright:

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

    Tree 2

    Uploaded by

    PK Tuber05
    The document discusses different types of binary trees including binary search trees. It defines binary trees, strict binary trees, complete binary trees, extended binary trees, and expression trees. It also covers binary tree representations using arrays and linked lists. Finally, it discusses tree traversals including in-order, pre-order and post-order traversals and provides algorithms to perform each type of traversal. It also describes how to construct and evaluate expression trees representing mathematical expressions.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 19

    UNIT IV

    TREES
    Syllabus
     General trees – Terminology – Representation of
    trees – Tree traversal- Binary tree –
    Representation – Expression tree – Binary
    tree traversal - Threaded Binary Tree - Binary
    Search Tree – Construction - Searching - Binary
    Search Tree- Insertion – Deletion - AVL trees –
    Rotation AVL trees – Insertion – Deletion - B-
    Trees – Splay trees - Red-Black Trees
    Binary Tree
     A tree in which every node can have a maximum of two
    children is called as Binary Tree.

     There are different types of binary trees and they are...


    ◦ Strictly Binary Tree
    ◦ Complete Binary Tree
    ◦ Extended Binary Tree
    Strictly Binary Tree
     A binary tree in which every node has either two or
    zero number of children is called Strictly Binary Tree
     Strictly binary tree is also called as Full Binary Tree or
    Proper Binary Tree or 2-Tree

     Strictly binary tree data structure is used to represent


    mathematical expressions. Such tree is called Expression
    Tree
    Complete Binary Tree
     A binary tree in which every internal node has
    exactly two children and all leaf nodes are at
    same level is called Complete Binary Tree.
     Complete binary tree is also called as Perfect
    Binary Tree
    Extended Binary Tree
     The strictly binary tree or full binary tree
    obtained by adding dummy nodes to a binary
    tree is called as Extended Binary Tree
    Binary Tree Representation
    ◦ Array Representation
    ◦ Linked List Representation
    Consider the following binary tree...
    Array representation
     We use a one dimensional array (1-D Array) to
    represent a binary tree.
     To represent a binary tree of depth 'n' using array
    representation, we need one dimensional array with a
    maximum size of 2n+1 - 1.
    Linked List Representation
     We use double linked list to represent a binary tree. In
    a double linked list, every node consists of three fields.
    Struct node
    {
    struct node * lc;
    int data;
    struct node * rc;
    };
    Binary tree Traversal
    Displaying (or) visiting order of nodes in a binary tree is called as
    Binary Tree Traversal.
    There are three types of binary tree traversals.
    ◦ In - Order Traversal
    ◦ Pre - Order Traversal
    ◦ Post - Order Traversal
    In-order Traversal
    Algorithm
    void inorder(struct node * root);
    {
    if(root != NULL)
    {
    inorder(root-> lc);
    printf("%d\t",root->data);
    inorder(root->rc);
    }
    }

    In-Order Traversal for above example of binary tree is


    I - D - J - B - F -A - G - K - C - H
    Pre-order Traversal
    Algorithm
    void Preorder(struct node * root);
    {
    if(root != NULL)
    {
    printf("%d\t",root->data);
    preorder(roo-> lc);
    preorder(root->rc);
    }
    }

    Pre-Order Traversal for above example of binary tree is


    A–B–D–I–J–F–C–G–K–H
    Post-order Traversal
    Algorithm
    void postorder(struct node * root);
    {
    if(root != NULL)
    {
    postorder(root-> lc);
    postorder(root->rc);
    printf("%d\t",root->data);
    }
    }

    In-Order Traversal for above example of binary tree is


    I – J – D – F – B – K – G – H – C –A
    Expression Tree
     A binary tree in which every node has either two or
    zero number of children is called Strictly Binary Tree
     Strictly binary tree is also called as Full Binary
    Tree or Proper Binary Tree or 2-Tree
     Strictly binary tree data structure is used to represent
    mathematical expressions.
     Expression tree is a binary tree in which each internal
    node corresponds to operator and each leaf node
    corresponds to operand so for example expression tree
    for 3 + ((5+9)*2) would be:
     Inorder traversal of expression tree produces infix
    version of given postfix expression (same with preorder
    traversal it gives prefix expression)
    Evaluating the expression
    represented by expression tree:
    Let t be the expression tree
    If t is not null then
    If t.value is operand then
    Return t.value
    A = solve(t.left)
    B = solve(t.right)
    // calculate applies operator 't.value'
    // on A and B, and returns value
    Return calculate(A, B, t.value)
     Construction of Expression Tree:
    Now For constructing expression tree we use a stack.
    We loop through input expression and do following for
    every character.
    1) If character is operand push that into
    stack
    2) If character is operator pop two values
    from stack make them its child and push
    current node again.
    At the end only element of stack will be
    root of expression tree.
    Solve Worksheet 2
    Thank You

    You might also like