Week 9

Quiz

• Collect homework
  • discuss

Trees

• Binary Trees
  • Concept
  • Draw
  • Terms:

·        node, root, left & right child, parent, leaf, sub-tree, depth, complete

• Usage

·        e.g. medical 20 questions

·        e.g. sorted list

• general tree
  • node may have any number of children
• tree implementation
  • complete binary tree as an array

·        root =[0], children of i = [2i+1],[2i+2], parent of i = [(i-1)/2]

·        limited by array, must be complete, etc.

• as dynamic nodes

·        draw picture

·        define class structure

• will be a big deal to decide if things go in node or tree class

• can also use a static class

·        basic ops, e.g.

isleaf(),

add(),

copytree(tnode

·        draw pictures of operations remove and add

·        lots of cases for remove node

·        show code for simple removal

·        do remove rightmost();

public node remrightmost()

{

            if(right == null)

                        return(left);

            else

                        right = right.remrightmost()

                        return this;

·        show how this works recursively, show stack

• tree traversal
  • pre-order, in-order, post-order – refers to when the root is processed
  • method

public void printtree()

{

            print node;

            if(left != null)

                        left.printtree();

            if(right != null)

                        right.printtree();

}

• show how works recursively
• show other orders
• write method to count the nodes in a tree

• hand out homework 6