Compsci Unit 8 Review

Recursion

when a method calls itself until some terminating condition is met (without loops)

Stacks

dynamic data structures that follow a Last In, First Out protocol

Queues

dynamic data structures that follow a First In, First Out protocol

.push()

adds an item to the top of the stack

.pop()

references and removes the item from the top of the stack

.isEmpty() stacks

returns true if the stack is empty

.enqueue()

adds an element to the end of a queue

.dequeue()

removes and returns the first element in the queue

.isEmpty() queues

returns true if there are no more elements in the queue

Linked Lists

data structures that consist of nodes that contain data and an address to the location of the next piece of data

head

the first node that contains no data and an address to the first piece of data

node

contains a piece of data and an address to the next piece of data

tail

the last node that just contains data and “null” address

Doubly Linked Lists

nodes contain data and two pointers. one pointer points to the next node. one pointer points to the previous node

Circular Linked Lists

the tail pointer is no longer null, instead it points back to the first element in the linked list

Trees

they belong to the graph family of data structures. the top node is connected to one or more nodes on the next level that leads to the shape of an upside down tree

Binary Trees

a tree that has at most two children

Binary Search Trees

a binary tree where a node’s left-hand child has a key less than the parent while the right-hand child has a key greater than the parent

Inorder Traversal

1. left hand subtree

2. visits current node

3. right hand subtree

Preorder Traversal

1. visits current node

2. left hand subtree

3. right hand subtree

Postorder Traversal

1. left hand subtree

2. right hand subtree

3. visits current node

Infix Notation

the operator is placed between two operands

Postfix Notation

the operator follows the operands

Prefix Notation

the operator comes before the operand

Children / child node

the nodes below a given node

Key

a data field of a node, which may be used to search for the node or perform other operations on it

Leaf

a node that has no children

Level

refers to how many generations the node is from the root

Height

number of edges from the top node to the deepest leaf

Parent

all nodes except from the root, which has no parent node, have exactly one edge running upward to their parent node

Path

suppose one wants to travel, from node to node, along the edges that link them. The sequence of nodes that are travelled is called a ______

Root

the node at the top of the tree

Subtree

Any node may be considered to be the root of a _____. That ______ will consists of the node’s descendants

Traversing

to visit all the nodes of the tree in some specified order

Visiting

to arrive at a node for the purpose of performing some operation on the node