Trees (chapter 8) Flashcards
Define a tree in terms of models and structure
A tree is an abstract model that stores element hierarchically
What does a tree consist of?
consists of nodes that have a parent-child relationship with the exception of the root which is a special node that has no parent. Along with possible subtrees
Define internal and external nodes
an internal node is a node that has a child/children. An external node is a node with no children, also known as a leaf
Define an edge
an edge is pair of nodes, (u,v) such that u,v have a parent-child relationship.
Define a path
a path is a sequence of nodes situated in such a manner that any 2 consecutive nodes in the sequence form an edge
In what 3 areas can trees be applied?
- Organization charts (CEO and employees under him/her)
- File systems. There is a root folder, I go to documents, then CSC, then lectures but there are many other paths that I can take
- Programming environments
Define a sub-tree
A tree consists of a node and its descendants. A tree can be a subtree of itself
Describe the depth of a tree.
- depth is described as the number of edges present from the root of a tree to the particular NODE in question (excluding the node)
- also defined as the number of ancestors a node has (excluding the node)
Give code on how to find the depth of a tree recursively
int depth(node v){
if v is root
return 0
else
return 1 + depth(parent(v))
}What is the height of a tree (hint, an external node has a height of 0)
The height of a tree is the largest depth of a node.
Give code to find the height of a node
int height(Node v){
if v isExternal
return 0
else
return 1 + max(height(child(v)))
}What ADT do we use to define a tree why is it useful
We use position ADT, why? Beats me
How is a single node in a tree represented?
They are represented by an object that stores an element, a parent of the node, and a sequence of children of the node
3 types of tree traversals?
Post order, pre-order and inorder traversal
What is a pre-order traversal and where can it be applied?
in a pre-order, a node is visited before its descendants.
the application would be printing a structured document, the headings and subheadings must be printed before the text can be printed.
Provide code for pre-order traversal
visit(v)
for each child of v, w
preOrder(w)
- Pre-order is called on each child of the node
What happens in a post-order traversal and what are the applications?
the descendants of a node are visited before the node itself
the application would be a computation of the size of files and their subdirectories. You have to first calculate the size of the deepest files and tally them up as you go, only at the end do you get the total size of the folder
code for post-order traversals?
for each child w, of v
postOrder(w)
visit(v)
all descendants visited before the node in question is visited
What is a binary tree and what are its properties(concerning children)
- A binary tree is a data structure with a parent node having at most 2 children nodes (0,1,2)
- The children of binary trees form an order per and can be distinguished as the left and right child
What is a proper binary tree?
It is a binary tree that has the restriction that an internal node must strictly have either 0 or 2 children
Define a binary tree in terms of recursion
A tree consisting of a single node, or the root has an ordered pair of children, each of which are a binary tree (being itself or having 2 children, thus a binary tree)
What are the applications of a binary tree?
- Decision-making. A yes or no tree
- Searching (?)
- Arithmetic expressions
What are the internal and external nodes of an arithmetic binary tree? Decision making?
- internal nodes are operands and external nodes are
* questions are the internal nodes(having yes/no answer), external nodes are the yes/no
How does a linked binary tree operate?
An object will store a reference to the element, the parent, the left child and the right child
Define a binary tree recursively
A tree with a single node, the root. Or whose root consists of children who form an ordered pair. Each of which form a tree
How is an inorder tree implemented and what are its applications?
Left subtree is visited before the parent, the right subtree is visited thereafter.
Application is drawing a binary tree
Provide psuedo-code for the inorder traversal
inOrder(Node v){
if(hasLeft(v)){
inOrder(v.left)
}
visit(v)
if(hasRight){
inOrder(v.right)
}
}
What is the Euler tour? How many times is each node visited?
Euler tour is a kind of traversal that includes special cases of the pre, in and post traverals. Each node is visited 3 times
What is a template method pattern? (3)
- generic algorithm that can be specialized by redefining certain steps
- implemented using an abstract java class
- visit methods are redefined by the subclasses
