Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    Trees

    Uploaded by

    AKHILA KHODAY
    This document defines and explains key terms related to tree data structures. It discusses nodes, edges, root, leaf and internal nodes. It also covers different types of binary trees like strictly binary, complete, almost complete and binary search trees.

    Copyright:

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

    Trees

    Uploaded by

    AKHILA KHODAY
    8 views28 pages
    This document defines and explains key terms related to tree data structures. It discusses nodes, edges, root, leaf and internal nodes. It also covers different types of binary trees like strictly binary, complete, almost complete and binary search trees.

    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 defines and explains key terms related to tree data structures. It discusses nodes, edges, root, leaf and internal nodes. It also covers different types of binary trees like strictly binary, complete, almost complete and binary search trees.

    Copyright:

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

    Trees

    Uploaded by

    AKHILA KHODAY
    This document defines and explains key terms related to tree data structures. It discusses nodes, edges, root, leaf and internal nodes. It also covers different types of binary trees like strictly binary, complete, almost complete and binary search trees.

    Copyright:

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

    Trees

    .
    What is Tree?
     Definition: A tree is a data structure which is a collection of
    Zero or more nodes and finite set of directed lines called
    branches that connects the nodes
    Node
     In tree data structure, every individual element is called
    as Node.
     Node in a tree data structure stores the actual data of that
    particular element and link to next element in hierarchical
    structure.
    .
     .
    Terminology

     In a tree data structure, we use the following terminology...


    1. Root
     In a tree data structure, the first node is called as Root Node.
    Every tree must have a root node.
     In any tree, there must be only one root node. We never have
    multiple root nodes in a tree.
    Left and Right subtree
     Left sub tree
    ◦ Tree which is connected to the left of the root.
     Right sub tree
    ◦ Tree which is connected to the right of the root.
    2. Edge
     In a tree, the connecting link between any two
    nodes is called as EDGE.

    In a tree with 'N' number of nodes there


    will be a maximum of 'N-1' number of
    edges.
    3. Parent

     The node which has a branch from it to any other node is


    called a parent node.
     Parent node can also be defined as "The node which has
    child / children".
    4. Child

     The node which has a link from its parent node is called as
    child node.
     In a tree, all the nodes except root are child nodes.
    5. Siblings

     In a tree data structure, nodes which belong to same Parent


    are called as SIBLINGS.
     In simple words, the nodes with the same parent are called
    Sibling nodes.
    6. Leaf

     In a tree data structure, the node which does not have a child
    is called as LEAF Node.
     In simple words, a leaf is a node with no child.
     In a tree data structure, the leaf nodes are also called
    as External Nodes. External node is also a node with no child.
    In a tree, leaf node is also called as 'Terminal' node.
    7. Internal Nodes

     In a tree data structure, the node which has at least one child
    is called as INTERNAL Node. In simple words, an internal node
    is a node with at least one child.
     External nodes
    8.Degree
     Total number of children of a node is called as DEGREE of that Node.
     In simple words, the Degree of a node is total number of children it has.
     The highest degree of a node among all the nodes in a tree is called as
    'Degree of Tree'
     In degree and Out degree
    9. Level

     The distance of a node from the root is called


    level of the node
    10. Height

     Maximum level of any leaf in the tree


    Binary tree
     A binary tree is a special type of tree data structure in which
    every node can have a maximum of 2 children.
     One is known as a left child and the other is known as right
    child.
    Not a binary tree
    Examples
     Binary tree
    Not a binary tree
     Types of binary trees 
    1) Strictly Binary Tree
    2) Complete Binary Tree
    3) Almost Complete Binary Tree
    4) Binary search tree
    Strictly Binary Tree
     Strictly Binary Tree is a Binary Tree in which
    every node has 0 or 2 children.
    examples
    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.
    examples

     .
    Almost Complete Binary Tree-
     An almost complete binary tree is a binary tree that
    satisfies the following 2 properties-
    ◦ All the levels are completely filled except possibly the last
    level.
    ◦ The last level must be strictly filled from left to right.
    .
    A binary search tree
      A binary search tree should satisfy following
    2 conditions:
    ◦ value of all the nodes in the left sub-tree should be
    less than or equal to the vale of the root.
    ◦ The value of all the nodes in the right sub should
    be greater than or equal to the value of the root.
    Example

    You might also like