• Main Menu
  • Trees


    Arrays, linked lists, stacks and queues are used to represent linear and tabular data. These structures are not suitable for representing hierarchical data.

    In hierarchical data we have

    • ancestors, descendants
    • superiors, subordinates, etc

    Family Structure

    Family Tree

    Business Corporate Structure

    Business Corporate Tree

    Federal Government Structure

    Federal Government Structure

    Introduction to Trees

    • Fundamental data storage structures used in programming
    • Combine advantages of ordered arrays and linked lists
    • Searching can be made as fast as in ordered arrays
    • Insertion and deletion as fast as in linked lists

    Tree characteristics

    • Consists of nodes connected by edges
    • Nodes often represent entities (complex objects) such as people, car parts etc.
    • Edges between the nodes represent the way the nodes are related.
    • It's easy for a program to get from one node to another if there is a line connecting them.
    • The only way to get from node to node is to follow a path along the edges.

    Tree Terminology

    • Root: node without parent (A)
    • Internal node: node with at least one child (A, B, C, F)
    • External node: (a.k.a. leaf) node without children (E, I, J, K, G, H, D)
    • Ancestors of a node: parent, grandparent, grand-grandparent, etc
    • Depth of a node: number of ancestors
    • Height of a tree: maximum depth of any node (3)
    • Descendant of a node: child, grandchild, grand-grandchild, etc
    • Degree of an element: no. of children it has
    • Subtree: tree consisting of a node and its descendants

    Tree and subtree

    • Path: traversal from node to node along the edges that results in a sequence
    • Root: node at the top of the tree
    • Parent: any node, except root has exactly one edge running upward to another node. The node above it is called parent.
    • Child: any node may have one or more lines running downward to other nodes. Nodes below are children.
    • Leaf: a node that has no children
    • Subtree: any node can be considered to be the root of a subtree, which consists of its children and its children's children and so on.
    • Visiting: a node is visited when program control arrives at the node, usually for processing.
    • Traversing: to traverse a tree means to visit all the nodes in some specified order.
    • Levels: the level of a particular node refers to how many generations the node is from the root. Root is assumed to be level 0.
    • Keys: key value is used to search for the item or perform other operations on it.

    Binary Trees

    • Every node in a binary tree can have at most two children.
    • The two children of each node are called the left child and right child corresponding to their positions.
    • A node can have only a left child or only a right child or it can have no children at all. Height of a binary tree
    • A binary tree is a tree with the following properties:

      • Each internal node has at most two children (exactly two for proper binary trees)
      • The children of a node are an ordered pair
    • We call the children of an internal node left child and right cild
    • Alternative recursive definition: a binary tree is either

      • a tree consisting of a single node, or
      • a tree whose root has an ordered pair of children, each of which is a binary tree
    • Applications:

      • arithmetic expressions
      • decision processes
      • searching

    Binary tree

    Arithmetic Expression Tree

    • Binary tree associated with an arithmetic expression

      • internal nodes: operators
      • external nodes: operands
    • Example: arithmetic expression tree for the expression (2 * (a – 1) + (3 * b))

    Expression tree

    Compiling arithmetic expressions

    We can represent an arithmetic expression such as

    (A + B) * (C + D) * 2 – X / Y as a binary tree, in which the leaves are constants or variables and the nodes are operations:A post order traversal then gives us the order in which the operations have to be carried out

    Properties of Proper Binary Trees

    Notation

    • n number of nodes
    • e number of external nodes
    • i number of internal nodes
    • h height

    Properties

    • e = i +1
    • n =2e -1
    • h <= i
    • h <= (n -1)/2
    • e <= 2h

    Got Something To Say:

    Your email address will not be published. Required fields are marked *

    C
    169 queries in 0.529 seconds.