September 25th, 2015

Trees

• A tree is a nonlinear structure in which elements are organized
  into a hierarchy.
• A tree is composed of a set of nodes in which elements are stored and edges that connect one node to another.
• Each node is at a particular level in the tree hierarchy.
• The root of the tree is the only node at the top level of the tree.
• There is only one root node in a tree.
• The nodes at lower levels of the tree are the children of nodes at the previous level.
• A node can have only one parent, but a node may have multiple children.
• Nodes that have the same parent are called siblings.
• The root node is the only node in a tree that does not have a parent.
• A node that does not have any children is called a leaf.
• The root is the entry point into a tree structure. We can follow a path through the tree from parent to child.
• We can follow a path through the tree from parent to child.
• A node is the ancestor of another node if it is above it on the path from the root.
• The level of a node is also the length of the path from the root to the node.
• This path length is determined by counting the number of edges that must be followed to get from the root to the node.
• The height of a tree is the length of the longest path from the root to a leaf.

Tree Types

• A tree that has no limit to the number of children a node may have is called a general tree.
• A tree that limits each node to no more than n children is referred to as an n-ary tree.
• A tree in which nodes may have at most two children is called a binary tree.
• A tree is considered to be balanced if all of the leaves of the tree are on the same level or at least within one level of each other.
• A balanced n-ary tree with m elements will have a height of log base n of m.
• A balanced binary tree with n nodes will have a height of log base 2 of n.

• A complete tree is related to the balance of a tree.
• A tree is complete if it is balanced and all of the leaves at the bottom level are on the left side of the tree.
• Another way to define this concept is that a complete binary tree has 2^k nodes at every level k except the last, where the nodes must be leftmost.
• An n-ary tree is considered full if all the leaves of the tree are at the same level and every node is either a leaf or has exactly n children.

(a) and (c)–are complete
Only (c) in Figure full

Homework:
Visit edmodo.com to answer the following questions
1. What is a tree?
2. What is a node?
3. What is the root of the tree?
4. What is a leaf?
5. What is an internal node?
6. Define the height of a tree.
7. Define the level of a node.

Read Tree implementation with arrays.

Classwork:

Stack: linked-list implementation

A Queue ADT
A queue is a linear collection whose elements are added on one end and removed from the other. Therefore, we say that queue elements are processed in a first in, first out (FIFO) manner. Elements are removed from a queue in the same order in which they are placed on the queue.

public interface QueueADT
{
// Adds one element to the rear of the queue
public void enqueue (T element);

// Removes and returns the element at the front of the queue
public T dequeue();

// Returns without removing the element at the front of the queue
public T first();

// Returns true if the queue contains no elements
public boolean isEmpty();

// Returns the number of elements in the queue
public int size();

// Returns a string representation of the queue
public String toString();
}

Assignment: Using the QueueADT interface, implement the Queue ADT according to the API below:

■ Queue elements are processed in a FIFO manner—the first element in is the first element out.
■ A queue is a convenient collection for storing a repeating code key.
■ Simulations are often implemented using queues to represent waiting lines.
■ A linked implementation of a queue is facilitated by references to the first and last elements of the linked list.
■ The enqueue and dequeue operations work on opposite ends of the collec- tion.
■ Because queue operations modify both ends of the collection, fixing one end at index 0 requires that elements be shifted.
■ The shifting of elements in a noncircular array implementation creates an O(n) complexity.
■ Treating arrays as circular eliminates the need to shift elements in an array queue implementation.

Assignments:
1. Create a system using a stack and a queue to test whether a given string is a palindrome (i.e., the characters read the same forward or backward).

2. Create a system to simulate vehicles at an intersection. Assume that there is one lane going in each of four directions, with stoplights facing each direction. Vary the arrival average of vehicles in each direction and the frequency of the light changes to view the “behavior” of the intersection.

Answer question about videos 2.3 and 2.4 from Classroom Salon.

Coming reading assignments:

Data Structures: Stacks and Queues

Stacks. A stack is a collection that is based on the last-in-first-out (LIFO) policy. By tradition, we name the stack insert method push() and the stack remove operation pop(). We also include a method to test whether the stack is empty, as indicated in the following API:

Video Lectures :
Stacks and Queues
Clients

Assignment:
Implement the ArrayStackOfIntegers ADT for Integers using arrays.

Other members that you need to implement:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayStackOfIntegers implements Iterable {
    private Integers[] items;  // holds the items
    private int n;             // number of items in stack
    public ArrayStackOfIntegers(int capacity) {
        items = (Integer[]) new Object[capacity];
    }

    public boolean isEmpty() {
        ----
    }

    public boolean isFull() {
        ----
    }

    public void push(Integer item) {
        ----
    }

    public Integer pop() {
        
    }

    public Iterator iterator() {
        return new ReverseArrayIterator();
    }

    // an iterator, doesn't implement remove() since it's optional
    private class ReverseArrayIterator implements Iterator {

    ----
    public void remove() 
    {}
    }
}

An example of Iterable

The files in this site are cleaned up a bit here.

Use the ArrayStackOfIntegers ADT  to work on these assignments:
ArrayStackOfIntegers ADT – Calculator
Design and implement a client to calculate the following postfix expression: 8 4 -3 * 1 5 + / *

 
ArrayStackOfIntegers ADT – Enhanced Calculator
 
StackCalculatorEnhanced

 

Classwork:
Lesson Videos – questions are posted

Homework
Undirected Graphs – Ex 4.1.1-4.1.3

Classwork:
1. At classroomSalon.com:
Video 11.4 has one question.
Please type “done” in edmodo.com when you answer it.

Homework:
At edmodo.com:
Summary and comparisons.

NOTE: Classroomsalom.com has gone mobil now!!!!