- Forward


Data Structures for Trees
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back SMYC Forward
  • Graph:
    • A set of vertices/nodes and a set of edges/links/arcs (each joining a pair of nodes)
  • Tree:
    • A connected graph with no circuits
N-ary Trees
Back SMYC Forward
  • Defined:
    • A directed tree in which each vertex has at most N "outbound" arcs and at most one "inbound" arc
  • Other Terminology:
    • The vertex incident to the inbound arcs is called the parent
    • The vertices incident to the outbound arcs are called the children
  • The Most Common Example:
    • Binary Tree
    • Hackles-BinaryTree
      (Courtesy of Hackles)
Binary Trees
Back SMYC Forward

An Example

binary_tree
Common Data Structures
Back SMYC Forward
  • N-ary Trees:
    • Contiguous structures (when the size is known)
    • Linked Structures
  • General Trees:
    • Linked structures
Contiguous Structures for N-ary Trees
Back SMYC Forward
  • An Example:
    • 3heap
  • A Contiguous Structure for this Example:
    • 45 41 42 35 29 38 34 22 11 40 9 18
Contiguous Structures for N-ary Trees (cont.)
Back SMYC Forward
  • Index Calculations:
    • parent(i) = (i - 1) / N
    • firstChild(i) = (i * N) + 1
    • lastChild(i) = (i * N) + N
  • Back to the Example:
    • The 42 is in position 2
    • Its parent is in position (2-1)/3 = 0
    • It's children are in positions 7 through 9
Linked Structures for Trees
Back SMYC Forward
  • Nodes:
    • Contain child nodes or pointers to child nodes
    • May contain a pointer to the parent node
  • Example:
    • linked_binary_tree
There's Always More to Learn
Back -