61B-25: Advanced Trees, incl. Geometric

HHZZ included in UCB-CS61B

2024-07-13 405 words 2 minutes

Contents

Traversals

Level Order

Traverse top-to-bottom, left-to-right (like reading in English):
We say that the nodes are ‘visited’ in the given order.

Depth First Traversals

Preorder, Inorder, Postorder
Basic (rough) idea: Traverse “deep nodes” (e.g. A) before shallow ones (e.g. F).

preorder

1
2
3
4
5
6


preOrder(BSTNode x) {
    if (x == null) return;
    print(x.key)
    preOrder(x.left)
    preOrder(x.right)
}

D B A C F E G

inorder

1
2
3
4
5
6


inOrder(BSTNode x) {
    if (x == null) return;
    inOrder(x.left)
    print(x.key)
    inOrder(x.right)
}

A B C D E F G

postorder

1
2
3
4
5
6


postOrder(BSTNode x) {
    if (x == null) return;
    postOrder(x.left)
    postOrder(x.right)
    print(x.key)
}

A C B E G F D

trick to think about

visitor pattern

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


interface Action<Label> {
   void visit(Tree<Label> T);
}

class FindPig implements Action<String> {
   boolean found = false;
   @Override
   void visit(Tree<String> T) {
      if ("pig".equals(T.label))
         { found = true; }
   }
}

1
2
3
4
5
6


void preorderTraverse(Tree<Label> T, Action<Label> whatToDo) {
   if (T == null) { return; }
   whatToDo.visit(T); /* before we hard coded a print */
   preorderTraverse(T.left, whatToDo);
   preorderTraverse(T.right, whatToDo);
}

1

preorderTraverse(someTree, new FindPig());

What is the runtime of a preorder traversal in terms of N, the number of nodes? (in code below, assume the visit action takes constant time)

Θ(N) : Every node visited exactly once. Constant work per visit.

Level Order Traversal

Iterative Deepening

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


public void levelOrder(Tree T, Action toDo) {
   for (int i = 0; i < T.height(); i += 1) {
      visitLevel(T, i, toDo);
   }
}

    // Run visitLevel H times, one for each level.
public void visitLevel(Tree T, int level, Action toDo) {
   if (T == null)
      { return; }
   if (lev == 0)
      { toDo.visit(T.key); }
   else {
      visitLevel(T.left(), lev - 1, toDo);
      visitLevel(T.right(), lev - 1, toDo);
   }
}