Scribd Logo
Upload

Welcome to Scribd!

  • 39 views

    Types of Trees

    Uploaded by

    isayashpbende26
    1. A tree data structure contains nodes connected by edges. The nodes can have child nodes, with leaf nodes being nodes without children. 2. Internal nodes are nodes that have at least one child node. The root is the topmost node, and the depth and height of nodes is measured by the number of edges from the root or other nodes. 3. Common tree types include general trees, binary trees where nodes have at most two children, and binary search trees where the left child is less than the parent and right child is greater than the parent.

    Copyright:

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

    Types of Trees

    Uploaded by

    isayashpbende26
    39 views23 pages
    1. A tree data structure contains nodes connected by edges. The nodes can have child nodes, with leaf nodes being nodes without children. 2. Internal nodes are nodes that have at least one child node. The root is the topmost node, and the depth and height of nodes is measured by the number of edges from the root or other nodes. 3. Common tree types include general trees, binary trees where nodes have at most two children, and binary search trees where the left child is less than the parent and right child is greater than the parent.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. A tree data structure contains nodes connected by edges. The nodes can have child nodes, with leaf nodes being nodes without children. 2. Internal nodes are nodes that have at least one child node. The root is the topmost node, and the depth and height of nodes is measured by the number of edges from the root or other nodes. 3. Common tree types include general trees, binary trees where nodes have at most two children, and binary search trees where the left child is less than the parent and right child is greater than the parent.

    Copyright:

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

    Types of Trees

    Uploaded by

    isayashpbende26
    1. A tree data structure contains nodes connected by edges. The nodes can have child nodes, with leaf nodes being nodes without children. 2. Internal nodes are nodes that have at least one child node. The root is the topmost node, and the depth and height of nodes is measured by the number of edges from the root or other nodes. 3. Common tree types include general trees, binary trees where nodes have at most two children, and binary search trees where the left child is less than the parent and right child is greater than the parent.

    Copyright:

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

    Tree Terminologies

    • Node
    • A node is an entity that contains a key or value and
    pointers to its child nodes.
    • The last nodes of each path are called leaf nodes or
    external nodes that do not contain a link/pointer to
    child nodes.
    • The node having at least a child node is called
    an internal node.
    • Edge
    It is the link between any two nodes.
    • Root
    It is the topmost node of a tree.
    • Height of a Node
    The height of a node is the number of edges
    from the node to the deepest leaf (ie. the
    longest path from the node to a leaf node).
    Height of node 1 = 2
    Depth of a Node
    • The depth of a node is the number of edges
    from the root to the node.
    Depth of 5 = 2 Depth o 3=1
    • Height of a Tree
    • The height of a Tree is the height of the root
    node or the depth of the deepest node.
    Height of Tree=2
    • Degree of a Node
    • The degree of a node is the total number of
    branches of that node.
    Degree of 2= 2 Degree of 3=0
    The node which is a descendant of some node is
    called as a child node.
    All the nodes except root node are child nodes.
    Nodes which belong to the same parent are called
    as siblings.
    The node which has at least one child is called as
    an internal node.
    Internal nodes are also called as non-terminal
    nodes.
    Every non-leaf node is an internal node.
    1) Child nodes
    2) Siblings
    3) Leaf nodes
    4) Internal nodes
    5) Degree of A, B, F
    6) Level of Tree
    7) Height of tree
    8) Depth of tree
    9) Height of C and E
    10) Depth of B and C
    Types of trees
    • 1. General Tree
    • If no constraint is placed on the tree’s
    hierarchy, a tree is called a general tree. Every
    node may have infinite numbers of children in
    General Tree. The tree is the super-set of all
    other trees.
    2. Binary Tree
    • A binary tree is a tree data structure where a
    node can have at most two child nodes
    (children). These two child nodes are known
    as the left child and right child.
    • 3. Binary Search Tree
    • Binary Search Tree (BST) is a binary tree
    extension with several optional restrictions.
    The left child value of a node should in BST be
    less than or equal to the parent value, and the
    right child value should always be greater than
    or equal to the parent’s value. This Binary
    Search Tree property makes it ideal for search
    operations since we can accurately determine
    at each node whether the value is in the left
    or right sub-tree.
    Binary Search Tree
    • 4. AVL Tree
    • AVL tree is a binary search tree self-balancing.
    On behalf of the inventors Adelson-Velshi and
    Landis, the name AVL is given. This was the
    first tree that balanced dynamically. A
    balancing factor is allocated for each node in
    the AVL tree, based on whether the tree is
    balanced or not.
    Click to add text

    AVL Tree
    • 43, 10, 79, 90, 12 (Binary Search Tree)
    Draw Binary Search tree for the following
    Ex.1) 10,7,14, 20, 1,5,8
    Ex.2) 18, 22,30, 13, 20, 25, 45, 10, 17, 14,18
    Ex.3) 6, 10, 14, 4, 8, 1, 3, 13, 7

    Q.1) List any four features of tree datastructure


    Q.2) List any four uses of tree data structure
    Q.3) List any four advantages of tree data
    structure

    You might also like