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 $l$ is # of leaves $i$ is # of internal nodes $h$ is height

$l=i+1\,\!$ $n=2l-1\,\!$ $h\leq i$ $h\leq {\frac {(n-1)}{2}}$ $l\leq 2^{h}$ $h\geq \log _{2}{l}$ $h\geq \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 $n$ is $2n$
• right child of node at index $n$ is $2n+1$
• parent of node at index $n$ is $\left\lceil {\frac {n-1}{2}}\right\rceil$