Week 4: Trees Flashcards
What are some applications of a tree data structure?
Organzation of a company
What are the following groupings called corresponding to the following tree:
Root node, parent nodes, sibling nodes, children nodes
For the following tree, what nodes are:
Descendants of B
Descendants of A
Ancestors of J
Ancestors of A
What is an internal node? An external/leaf node?
What is the depth of a node? Height of a tree?
What are the following:
Depth of a tree
Height of a tree
Degree of a node
The degree of all nodes of a tree is equal to…
The number of edges
What is a subtree?
What is an odered tree?
Example of ordered trees:
What are unordered trees? Examples.
The number of nodes in a tree is equal to…
The number of edges + 1
The Tree ADT contains what methods?
What is the algorithm for computing the height of a tree?
Height of a tree algorithm with call stack:
What is preorder traversal? What is the algorithm?
What is postorder traversal? What is the algorithm?
What traversal would you use for the following? Why? What is the algorithm.
Preorder traversal
What travrsal would you use for the following? Why? What is the algorithm?
What is a binary tree? What properties must a binary tree have?
For binary tree, what is the number of leaves equal to?
For binary trees:
The number of nodes at level i is equal to?
The number of leaves is equal to?
What methods do the BinaryTree ADT have?
What is an inorder traversal? What is the algorithm?
Example of the three different types of traversals:
Example of PRINTING an arithmetic expression using inorder traversal
Example of EVALUATING an arithmetic expression using a binary tree inorder traversal:
What does a linked structure of a NON-binary tree look like?
What does a linked structure of a binay tree look like?
