LAB 11

Topic: Trees

Tasks

Task 0

Implement tree structure

class TNode{
    int key;
    TNode left;
    TNode right;
}

class Tree{
    TNode root;

    ....


}

Task 1

Compute number of nodes in a tree

int noOfNode();


recursive idea:
    #leftSubTree+#rightSubTree+1

Task 2

Find maximal key

int noOfNode();


recursive idea:
    max{leftSubTree,rightSubTree,key}

Types of trees

• Heap

  • Characteristics: parent is greater then children
  • => Root is maximum
  • for binary heap
  • getMax: 1
  • popMax: log n
  • addElement: log n
  • height: log n

  • similarly one can have min heap

  • there is also the heap: part of memory for dynamic allocation

• Binary Search Tree

  • Characteristics: all elements in left sub tree are smaller
    all elements in right sub tree are greater
  • add element: log n (in average)
  • getRoot: log n (in average)
  • problem: can be become imbalanced
  • easy to implement

• what is a complete tree

• what is an almost complete tree
• if depth is n how many elements

Traversals of trees

• 3 types of depth-first traversal

• pre-order

  • idea
    • print current node (start in root)
    • traverse left
    • traverse right
  • E.g.,
    1
    | \
    2 9
    |\ | \
    3 6 A D
    |\ |\ |\ |\
    45 78 BC EF

• in-order

  • idea
    • traverse left
    • print current node (start in root)
    • traverse right
  • E.g.,
    8
    | \
    4 C
    |\ | \
    2 6 A E
    |\ |\ |\ |\
    13 57 9B DF

• post-order

  • idea
  • traverse left
    • traverse right
    • print current node (start in root)
  • E.g.,
    8
    | \
    7 F
    |\ | \
    3 6 B E
    |\ |\ |\ |\
    12 45 9A CD

• Breadth-First Search BFS

  • E.g.,
    1
    | \
    2 3
    |\ | \
    4 5 6 7
    |\ |\ |\ |\
    89 AB CD EF

• references: http://en.wikipedia.org/wiki/Tree_traversal

Implementations of Tree Traversals

• How to implement traversals?

• Which abstract data-types?

• Stack (LIFO)

• Stacks implement a lifo policy (= last in, first out)

  • pre/post/in-order

• Task 3a) Implement pre-order 10 min

• Task 3b) Implement in-order 5 min

• Task 3c) Implement post-order 1 min

• For preorder etc, one needs lifo, i.e., stacks, which once gets
  for free by way of the recursion stack in Java.

Alg

    x-order(node)

     if node == null then return
        (a) print(node)            
        (b) x-order(node.left) 
        (c) x-order(node.right)

• If we exchange the order of (a) (b) and (c)?

• How to implement using stacks?

• How to implement a stack?

  • lists: adv/disadv
  • array: adv/disadv

• Breadth-First Search DFS

• Give students 5 min

• We need to implement Queue (FIFO)?

• Queues implement a fifo policy (= first in, first out)

• Give students 10 min

Alg

Class Qnode{
    Qnode next
    int   val
}

Class Queue{
    QNode head 
          tial

Boolean empty()

void enqueue(int value)

    Qnode  qn  = new Qnode(value,null)

    if empty
        head = tail = qn
    else
        tail.next = qn
        tail = qn


int dqueue()
    // take the last element in the list
}

• Now, how to implement BFS one?
• Using queue

Alg

    levelorder(root)
      q = empty queue
      q.enqueue(root)
      while not q.empty do
        node := q.dequeue()
        visit(node)
        if node.left ≠ null then
          q.enqueue(node.left)
        if node.right ≠ null then
          q.enqueue(node.right)

• What is Priority Queue?
• Is it different from Heap?
• How else we can implement PQ?

Serialization problem

Q: How to store BST such that after we read the elements of the tree using sequentially we again get the same tree?

We want a serialization method such that

Tree = array2BST ( serialize (Tree))

• Show an example

• Solution: Do it in pre-order

• explain the problem…