Scribd Logo
Upload

Welcome to Scribd!

  • 21 views

    Array Representation

    Uploaded by

    21951a2104
    This document discusses binary tree data structures. It defines a binary tree as a tree where each node has at most two children, called left and right children. It describes the key parts of a binary tree like the root node, parent node, child nodes, siblings, edges, leaf nodes, subtrees, depth, height, levels, degree of a node, and NULL nodes. It also explains two common representations of binary trees - the dynamic node representation using linked lists, and the array representation which stores tree elements in a sequential array. It provides examples of how the child-parent relationships would be represented in an array.

    Copyright:

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

    Array Representation

    Uploaded by

    21951a2104
    21 views6 pages
    This document discusses binary tree data structures. It defines a binary tree as a tree where each node has at most two children, called left and right children. It describes the key parts of a binary tree like the root node, parent node, child nodes, siblings, edges, leaf nodes, subtrees, depth, height, levels, degree of a node, and NULL nodes. It also explains two common representations of binary trees - the dynamic node representation using linked lists, and the array representation which stores tree elements in a sequential array. It provides examples of how the child-parent relationships would be represented in an array.

    Original Title

    array representation

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses binary tree data structures. It defines a binary tree as a tree where each node has at most two children, called left and right children. It describes the key parts of a binary tree like the root node, parent node, child nodes, siblings, edges, leaf nodes, subtrees, depth, height, levels, degree of a node, and NULL nodes. It also explains two common representations of binary trees - the dynamic node representation using linked lists, and the array representation which stores tree elements in a sequential array. It provides examples of how the child-parent relationships would be represented in an array.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    21 views6 pages

    Array Representation

    Uploaded by

    21951a2104
    This document discusses binary tree data structures. It defines a binary tree as a tree where each node has at most two children, called left and right children. It describes the key parts of a binary tree like the root node, parent node, child nodes, siblings, edges, leaf nodes, subtrees, depth, height, levels, degree of a node, and NULL nodes. It also explains two common representations of binary trees - the dynamic node representation using linked lists, and the array representation which stores tree elements in a sequential array. It provides examples of how the child-parent relationships would be represented in an array.

    Copyright:

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

    BINARY TREE

    REPRESENTATION ARRAY
    REPRESENTATION
    21951A2104
    AKSHAY
    Aero-2A
    What is binary tree?
    ■ Binary Tree is defined as a tree data structure where each node has at most
    2 children. Since each element in a binary tree can have only 2 children, we
    typically name them the left and right child.
    Parts of binary tree.
    ■ Root: The root of a tree is the topmost node of the tree that has no parent node. There is only
    one root node in every tree.
    ■ Parent Node: The node which is a predecessor of a node is called the parent node of that node.
    ■ Child Node: The node which is the immediate successor of a node is called the child node of
    that node.
    ■ Sibling: Children of the same parent node are called siblings.
    ■ Edge: Edge acts as a link between the parent node and the child node.
    ■ Leaf: A node that has no child is known as the leaf node. It is the last node of the tree. There can
    be multiple leaf nodes in a tree.
    ■ Subtree: The subtree of a node is the tree considering that particular node as the root node.
    ■ Depth: The depth of the node is the distance from the root node to that particular node.
    ■ Height: The height of the node is the distance from that node to the deepest node of that subtree
    ■ Height of tree: The Height of the tree is the maximum height of any node. This is the same as the
    height of the root node.
    ■ Level: A level is the number of parent nodes corresponding to a given node of the tree.
    ■ Degree of node: The degree of a node is the number of its children.
    ■ NULL: The number of NULL nodes in a binary tree is (N+1), where N is the number of nodes in
    a binary tree.
    Types of binary tree representation.
    Trees can be represented in two ways as listed below:
    ■ Dynamic Node Representation (Linked Representation):
    Binary trees in linked representation are stored in the memory as linked lists.
    These lists have nodes that aren’t stored at adjacent or neighboring memory
    locations and are linked to each other through the parent-child relationship
    associated with trees.
    ■ Array Representation (Sequential Representation):
    Although it is simpler than linked representation, its inefficiency makes it a
    less preferred binary tree representation of the two. The inefficiency lies in
    the amount of space it requires for the storage of different tree elements. The
    sequential representation uses an array for the storage of tree elements.
    Array representation of a binary tree.
    ■ Case 1:(node is at ith index)
    Left child at= [2*i+1]
    Right child at=[2*i+2]
    Parent would be at: [i-1/2]
    1 2 3 4 5 6 7
    ■ Case 2:(node is at ith index) 1 2 3 4 5 6 7
    left child at = (2*i)
    right child at = (a*i)+1]
    Parent at =[i/2]
    Note : after getting the parent value we need
    to take the floor of it.

    You might also like