Category Archives: Object Oriented Principles

• A nonlinear linked list in which each node may point to 0, 1, or two other nodes.
• Each node contains one or more data fields and two pointers.
• Tree pointer – Points to the first node in the binary tree.
• Root node – the node at the top of the tree.
• Leaf nodes – nodes that have no children.
• Child nodes, children – nodes below a given node
• Parent node – node above a given node.
• Subtree – portion of a tree from a node down to the leaves

Usage

• Binary search tree – data organized in a binary tree to simplify searches.
• Left subtree of a node contains data values < the data in the node.
• Right subtree of a node contains values > the data in the node.

Searching in a Binary Tree

• Start at root node
• Examine node data
  • Is it the desired value?
  • Else is desired data < node data? Repeat step 2 with left subtree
  • Else is desired data > node data? Repeat step 2 with right subtree
• Continue until desired value found or NULL pointer reached.

Binary Search Tree Node

• A node in a binary tree is like a node in a linked list, with two node pointer fields

	<li>struct TreeNode

{

int value;

TreeNode *left;

TreeNode *right;
}

Creating a New Node

• Allocate memory for new nodenewNode = new TreeNode;
• Initialize the contents of the nodenewNode – > value = num;
• Set the pointers to NULLnewNode – > Left= newNode – > Right

  = NULL;

Inserting a Node

• If tree is empty, insert the new node as the root node.
• Else compare new node against left or right child, depending on whether data value of new node is < or > root node.
• Continue comparing and choosing left or right subtree until NULL pointer found.
• Set this NULL pointer to point to new node.

Traversing a Binary Tree

• Inorder
  • Traverse left subtree of node
  • Process data in node
  • Traverse right subtree of node
• Preorder
  • Process data in node
  • Traverse left subtree of node
  • Traverse right subtree of node
• Postorder
  • Traverse left subtree of node
  • Traverse right subtree of node
  • Process data in node

Searching in a Binary Tree

• Start at root node, traverse the tree looking for value.
• Stop when value found or NULL pointer detected
• Can be implemented as a bool function

Deleting a Node from a Binary Tree – Leaf Node

• If node to be deleted is a leaf node, replace parent node’s pointer to it with a NULL pointer, then delete the node.

Deleting a Node from a Binary Tree – One Child

• If node to be deleted has one child node, adjust the pointers so that parent of node to be deleted points to child of node to be deleted, then delete the node.

Deleting a Node from a Binary Tree – Two Children

• If node to be deleted has left and right children,
  • Promote one child to replace the deleted node
  • Find the correct position for other child in subtree of promoted child

• Recursive function contains a call to itself.
• Reduce a complex problem to a simpler problem to be solved.
• Simpler-to-solve problem is known as the base case.
• Recursive calls stop when the base case is reached.
• Must always include a test to determine if another recursive call should be made, or if the recursion should stop with this call.
• Breaking a problem down into smaller problems until the problem can be solved.

Calling Recursive Function

• Each time a recursive function is called, a new copy of the function runs, with new instances of parameters and local variables created.
• As each copy finishes executing, it returns to the copy of the function that called it.
• When the initial copy finishes executing, it returns to the part of the program that made the initial call to the function.

Types of Recursion

• Direct – a function calls itself
• Indirect – function A calls function B, and function B calls function A

Linked List

• Can be members of a linked list class.
• Uses a pointer to visit each node to count the nodes in a linked list
  • pointer starts at head of list
  • if pointer is NULL, return 0 (base case)else return 1 + number of nodes in the list pointed to by current node
• Contents of a List in reverse order
  • pointer starts at head of list
  • if the pointer is NULL, return (base case)
  • If the pointer is not NULL, advance to next node
  • Upon returning from recursive call, display contents of current node.

Recursive Binary Search Function

• If middle element of array is desired value, the value is found.
• Else if the middle element is too large, repeat binary search in first half of array segment.
• Else if the middle element is too small, repeat binary search on the second half of array segment.

QuickSort Algorithm

• Recursive algorithm that can sort an array or a linear linked list.
• Determines an element or node to use as pivot value.
• Once pivot value is determined, values are shifted so that elements in sublist 1 are < pivot and elements in sublist 2 are > pivot
• Algorithm then sorts sublist1 and sublist2
• Base case: sublist has size 1

Exhaustive & Enumeration Algorithm

• Search a set of combinations to find an optimal one
• Uses the generation of all possible combinations when determining the optimal one.

Recursion vs. Iteration

• Recursion
  • Models certain algorithms most accurately.
  • Results in shorter, simpler functions.
  • May not execute very efficiently.
• Iteration
  • Executes more efficiently than recursion.
  • Harder to code or understand.

• FIFO – (First In, First Out)
• Static: fixed size, implemented as array
• Dynamic: variable size, implemented as linked list

Queue Locations & Operations

• rear – position where elements are added
• front – position from which elements are removed
• enqueue – add an element to the rear of the queue
• dequeue – remove an element from the front of a queue

Dequeue

• When removing an element from a queue, the remaining elements must shift to front.
• Move the front index as elements are removed

Dynamic Queues

• Can be implemented using a linked list
• Allows dynamic sizing.
• Queue operations implementation are programmable.

STL deque & queue Containers

• deque – double-ended queue which has member functions to enqueue (push_back) and dequeue (pop_front)
• queue – container ADT that can be used to provide queue as a vector, list or dequeue. Has member functions to enqueue (push) and deque (pop)

Defining a queue

• Defining a queue of chars, named cQueue, implemented using a deque:deque <char> cQueue;
  • implemented using a queue

    queue <char> cQueue;

  • implemented using a list

    queue <char, list<char> > cQueue;