AH

Tree Data Structures

Trees Overview

  • Trees are non-linear and hierarchical data structures.
  • Similarities to botanical trees:
    • Root: Topmost node in the tree.
    • Branches: Connections between nodes.
    • Leaves: Nodes with no children, located at the bottom of the tree.
  • Hierarchical representation: The root is at the top, leaves at the bottom, which helps in representing hierarchical relationships.

Key Properties of Trees

  • Root: The topmost node of the tree.
  • Children: Elements directly under a node.
  • Parent: Element directly above a node.
  • Leaves: Elements with no children.

Tree Components and Concepts

  • Nodes: Include root, parent, child, and leaf nodes.
  • Edges: Connection between nodes; can be a left or right child.
  • Height: The length of the longest path from the root to a leaf (e.g., for a tree of height 2, there are 3 levels: 0, 1, 2).

Binary Trees

  • Definition: A binary tree has at most two children for each node.
  • Visual representations show that binary trees can have different structures while containing the same nodes.

Binary Tree Classifications

  • Full Binary Tree:

    • A binary tree where every node has either 0 or 2 children.
    • Example: A tree of height $h$ where all leaves are at level $h$.

  • Complete Binary Tree:

    • Every level is completely filled, except possibly the last, which is filled from left to right.
    • Nodes at level $h-1$ and above have two children each.

Properties of Binary Trees

  • Maximum number of nodes at level $L$ is given by: 2^L.
    • Examples:
    • Level 0: Max nodes = 2^0 = 1
    • Level 1: Max nodes = 2^1 = 2
    • Level 2: Max nodes = 2^2 = 4
  • Maximum number of nodes in a binary tree of height $h$ is: 2^{h+1} - 1.

Balanced Binary Trees

  • A binary tree is balanced if the height difference of the left and right subtrees of any node is at most 1.
  • Properties:
    • All full binary trees are complete.
    • All complete binary trees are balanced.

Summary of Terminology

  • General Tree: A set of nodes with a root and general subtrees.
  • Parent and Child Nodes: Relationships between nodes.
  • Leaf: A node without children.
  • Siblings: Nodes sharing a parent.
  • Ancestor and Descendant: Relationship on the path from root to leaf.
  • Subtree: A tree consisting of a node and its children.
  • Height: The number of edges in the longest path from root to leaf.

Tree Representation Methods

  1. Array Based:

    • A binary tree is stored in an array where:
      • For any node at index $i$:
      • Left child is at index 2*i+1
      • Right child is at index 2*i+2
      • Parent is at index (i-1)/2
    • Pros: Memory efficient and simple implementation.
    • Cons: Not efficient for trees that are not complete, with limitations on insertion, deletion, and traversal.

  2. Class Based:

    • Nodes are defined as objects, typically with attributes for value, left child, and right child.

Tree Traversal Methods

  • Preorder Traversal:

    • Visit Root, Left, Right recursively.
    • Implementation illustrates recursion through visits to the current node followed by left and right subtrees.

  • Inorder Traversal:

    • Visit Left, Root, Right recursively.
    • Implementation details on recursively visiting left subtree, current node, and right subtree.

  • Postorder Traversal:

    • Visit Left, Right, Root recursively.
    • Focus on visiting child nodes before the current node.

Exercise

  • Determine the preorder, inorder, and postorder traversal results for the binary tree with nodes: a, b, c, d, e, f, g.