Unit 11 -- Csc 115 Spring 2005 SO1/S02
Learning Objectives for this unit
- To learn how to use and create ADTs for trees and binary trees
- Be able to use and implement the ADT operations and the complexity
of the different operations
- Understand and be able to implement the different kinds of tree traversals
- Understand the essence of Binary Search Trees
Learning Resources for this week
Lecture slides:
11-Trees.ppt
Sample programs as found in the source directory of this project
(see the activities below).
Reading Assignment:
Read Chapter 6 (you can omit 6.3.5 and 6.4.4)
Activities:
Short Answer Questions
- What operations would you expect a Binary Tree ADT to provide?
- Draw a proper binary tree that has 16 nodes with some arbitrary elements in it.
Show a preorder, postorder, inorder and levelorder traversals of your
made up tree
Problems in the textbook, Chapter 6:
Coding Questions
- Write the code for a TreeNode class, where each
node has a parent and each node has n children stored as a vector
Your TreeNode class will have the following public interface:
public class TreeNode{
public TreeNode ();
public TreeNode (int d); {
public void addChild(TreeNode child);
public Vector getChildren();
public TreeNode getParent();
public void setParent(TreeNode parent);
public int getData();
public void setData(int data);
public int getNumDescendants();
public void setNumDescendants(int n);
public String toString(); // should print all descendants of the node
// also add a main method to test your code!
(Note the solution to this one has been provided, but try it first!
TreeNode.java
- Examine the DynamicTree examples, see the suggested exercises in it:
DynamicTree.java
- The RecursiveTree example shows how to create a tree recursively, can you implement
the same functionality using iteration? See
- The TreeMap example also has many exercises in it. See
TreeMap.java
Go to the course website