Chapter 4 Trees and Graphs Flashcards
Tree
A data structure composed of nodes: one root node which can have zero or more child nodes, each of which can have zero or more child nodes pg 100
Binary Tree
A tree in which each node can only have up to two children pg 101
Binary Search Tree
A binary tree for which every node has all left children with a lesser value and all right children with a greater value. pg 101
Complete Binary Tree
A Binary tree for which each level is completely filled except possibly the last level which must be filled left to right. pg 102
Full Binary Tree
I Binary tree for which each node either has zero or two children pg 102
Perfect Binary Tree
A binary tree that is both full and complete pg 102
In-Order Traversal
A binary tree traversal that will visit the left node, current node, then right node Pg 103
Pre-Order Traversal
Binary search which visits the current node before visiting its children pg 103
Post-Order Traversal
A binary search in which the the current node is visited after all of its children pg 103
Min-Heap
A complete binary tree where the root has the lowest value in the whole tree pg 103
Trie (Prefex Tree)
An n-ary treee where each node contains a character and a path down the tree forms a word pg 105
Graph
A collection of nodes with connections to other nodes pg 105
Adjacency List
The most common way to represent a graph, each node stores a list of nodes adjacent to it pg 106
Adjacency Matrix
A representation of a graph with an NxN boolean matrix, a value of true represents an adjacency pg 106
Depth First Search
A graph search which searches each branch completely before searching the next branch pg 107
