Scribd Logo
Upload

Welcome to Scribd!

  • 36 views

    Data Structures (Binary Trees)

    Uploaded by

    Mohammad Zawar
    This document discusses binary trees, including their memory representation, types of traversals (pre-order, in-order, post-order, and level-order), and binary expression trees. Binary trees have at most two children per node and can be represented sequentially or via links. Traversals involve visiting each node once in a specific order, such as left-root-right for in-order traversal. Binary expression trees are binary trees where internal nodes represent operators and leaves represent operands.

    Copyright:

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

    Data Structures (Binary Trees)

    Uploaded by

    Mohammad Zawar
    36 views21 pages
    This document discusses binary trees, including their memory representation, types of traversals (pre-order, in-order, post-order, and level-order), and binary expression trees. Binary trees have at most two children per node and can be represented sequentially or via links. Traversals involve visiting each node once in a specific order, such as left-root-right for in-order traversal. Binary expression trees are binary trees where internal nodes represent operators and leaves represent operands.

    Original Title

    Data structures (Binary Trees)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses binary trees, including their memory representation, types of traversals (pre-order, in-order, post-order, and level-order), and binary expression trees. Binary trees have at most two children per node and can be represented sequentially or via links. Traversals involve visiting each node once in a specific order, such as left-root-right for in-order traversal. Binary expression trees are binary trees where internal nodes represent operators and leaves represent operands.

    Copyright:

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

    Data Structures (Binary Trees)

    Uploaded by

    Mohammad Zawar
    This document discusses binary trees, including their memory representation, types of traversals (pre-order, in-order, post-order, and level-order), and binary expression trees. Binary trees have at most two children per node and can be represented sequentially or via links. Traversals involve visiting each node once in a specific order, such as left-root-right for in-order traversal. Binary expression trees are binary trees where internal nodes represent operators and leaves represent operands.

    Copyright:

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

    BINARY TREE In DATA

    STRUCTURES

    Instructor:
    Ms.Dur-e-Shawar Agha
    ROAD MAP
     Introduction to Binary Tree

     Memory Representation of Binary Tree

     Tree Traversals
    Binary Tree

    o A tree whose elements have at most 2 children is called a binary tree.


    o Since each element in a binary tree can have only 2 children, we typically name
    them the left and right child.
    o A Binary Tree node contains following parts.
    • Data
    • Pointer to left child
    • Pointer to right child
    Representing Binary Tree in Memory
    Let T be a Binary Tree. There are two ways of representing T in the memory as follow

    1. Sequential Representation of Binary Tree.

    2. Link Representation of Binary Tree.


    1. Link Representation of Binary Tree
    Example
    2. Sequential Representation of Binary Tree
    Example
    Tree Traversal
    Tree traversal (also known as tree search) is a form of graph traversal and refers to the
    process of visiting (checking and/or updating) each node in a tree data structure, exactly
    once. Such traversals are classified by the order in which the nodes are visited.”
    Tree Traversal Algorithms can be classified broadly in the following two categories by the
    order in which the nodes are visited:

    1. Depth-First Search (DFS) Algorithm: It starts with the root node and first visits all
    nodes of one branch as deep as possible of the chosen Node and before
    backtracking, it visits all other branches in a similar fashion. There are three sub-
    types under this, which we will cover in this article.
    • In-order Traversal
    • Pre-order Traversal
    • Post-order Traversal
    Contd….

    2. Breadth-First Search (BFS) Algorithm: It also starts from the root node and visits all
    nodes of current depth before moving to the next depth in the tree. We will cover
    one algorithm of BFS type in the upcoming section.

    • Level-order Traversal
    1. Depth First search (DFS)

    Preorder Traversal
    • Algorithm
    i. Visit the root
    ii.Traverse the left sub tree i.e. call Preorder (left sub tree)
    iii.Traverse the right sub tree i.e. call Preorder (right sub tree)
    Root → Left → Right
    Contd….

    Consider the following example:


    Contd….

    Inorder Traversal
    • Algorithm
    i. Traverse the left sub tree i.e. call Inorder (left sub tree)
    ii. Visit the root
    iii. Traverse the right sub tree i.e. call Inorder (right sub tree)

    Left → Root → Right


    Contd….

    Consider the following example-


    Contd….

    Postorder Traversal
    • Algorithm
    i. Traverse the left sub tree i.e. call Postorder (left sub tree)
    ii. Traverse the right sub tree i.e. call Postorder (right sub tree)
    iii.Visit the root

    Left → Right → Root


    Contd….

    Consider the following example-


    2. Breadth First search (BFS)

    Level-Order Traversal-
    Breadth First Traversal of a tree prints all the nodes of a tree level by level.
    Example
    Implementation of Binary Tree

    Binary Expression Tree

    The expression tree is a binary tree in which each internal node corresponds to the
    operator and each leaf node corresponds to the operand.

    Example
    a + (b * c) + d * (e + f)
    Activity#01

    If the binary tree in figure is traversed in inorder, preorder and postorder then the order in
    which the nodes will be visited is ____?
    Activity#02

    Draw the binary expression tree for the following expression

    a. (3 * 7) + 9

    b. (3 + 2)^3 / (46 - 12)

    c. (NOT A) AND (B OR C)
    SUMMARY
     Introduction to Binary Tree

     Types of Binary Tree

     Tree Traversal

     Binary Expression Tree

    You might also like