CSCE 221 Chapter 6

« previous | Thursday, February 3, 2011 | next »

Trees

root

node without any children

internal node

any node with at least one child

leaf

any node without any children

ancestor

the parent, grandparent, great grandparent, etc. of a node

depth

number of ancestors

height

maximum depth of any node

descendant

children, grandchildren, great grandchildren, etc.

Methods for ADT:

• int size()
• bool isEmpty()
• ObjectIterator elements()
• PositionIterator positions()
• Position root
• Position parent(p)
• PositionIterator children(p)
• bool isInternal(p)
• bool isLeaf(p)
• bool isRoot (p)
• void swapElements(p,q)
• Object replaceElement(p, o)

Traversing Trees

Preorder Traversal

A node is visited before its descendants

def preOrder(v)
  visit(v)
  children(v).each { |w| preOrder(w) }
end

Postorder Traversal

A node's children are visited before the node itself

def postOrder(v)
  children(v).each { |w| preOrder(w) }
  visit(v)
end

Binary Trees

class BinaryTree : Tree { /* ... */ };

Every internal node has 2 children: left and right

• Decision-making
• Searching
• Arithmetic/Logical expressions

Properties

$n$ is # of nodes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l} is # of leaves Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} is # of internal nodes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} is height

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l=i+1\,\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2l-1\,\!} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \le i} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \le \frac{(n-1)}{2}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l \le 2^h} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \ge \log_2{l}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h \ge \log_2(n+1)-1}

Traversal (cont'd)

Inorder Traversal

(Binary Trees only)

A node is visited after its left subtree and before its right subtree.

def inOrder(v)
  inOrder(v.leftChild) if v.isInternal?
  visit(v)
  inOrder(v.rightChild) if v.isInternal?
end

Euler Tour Traversal

Kind of a generalization of all 3:

1. Visit node from "left" (preorder)
2. Visit node's left children
3. Visit node again from "bottom" (inorder)
4. Visit node's right children
5. Visit node again from "right" (postorder)

Exercise

       E
   X       N
 A   U
M F

Draw a binary tree T such that:

1. Each internal node stores a single character
2. preorder traversal yields EXAMFUN
3. inorder traversal yields MAFXUEN

Vector Implementation

• root stored at index 1 (index 0 is empty)
• left child of node at index Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n}
• right child of node at index Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n+1}
• parent of node at index Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\lceil \frac{n-1}{2} \right\rceil}