1
A collection where each node can have from 0 to 2 children is called a
___________.
A. Stack
A node that does not have a parent is called the ______ of a tree.
A. foot
A tree is a nonlinear structure whose elements are organized into a __________.
A. stack
The simulated link strategy allows array positions to be allocated contiguously
regardless of the _________ of the tree.
A. size
In general, a balanced n-ary tree with m elements will have height _______.
D. lognn
There are four basic methods for traversing a tree: preorder, inorder, postorder,
and level-order.
A. Top down, bottom up, inorder, and postorder
_________ traversal means visit the node, then the left child, then the right child.
D. level-order
2
_________ traversal means visit the left child, then the node, then the right child.
A. preorder
________ traversal means visit the left child, then the right child, then the node.
A. preorder
___________ traversal means visit the nodes at each level, one level at at time,
starting with the root.
A. preorder
In the computational strategy to implement a tree with an array, the children of
node n are stored at 2n + 1 and 2(n + 1) respectively.
A. 2n + 1
B. 2n + 2
A node that has both a parent and at least one child is called a(n) __<internal>__
node.
A
B
C
3
What is the height of the tree shown above? 2
For the binary tree shown below, list the elements in the order generated by an
InOrder traversal.
For the binary tree shown below, list the elements in the order generated by an
PreOrder traversal.
For the binary tree shown below, list the elements in the order generated by an
PostOrder traversal.
B
C
D
F
hierarchy.
contiguously regardless of the completeness of the tree.
D
F
E
A
4
Preorder traversal means __<visit the node, then the left child, then the right
child>__.
Inorder traversal means __<visit the left child, then the node, then the right
child>__.
Postorder traversal means __<visit the left child, then the right child, then the
node>__.
Level-order traversal means __<visit the nodes at each level, one level at at time,
starting with the root>__.
True/False. The binary tree shown above is balanced.
a Binary Tree.
as a find operation for binary search tree without the balance assumption is O(n).
True/False. A tree is a nonlinear structure whose elements are organized into a
hierarchy.
allocated contiguously regardless of the completeness of the tree.
True/False. In general, a balanced n-ary tree with m elements will have height
lognm.
the node.
5
right child.
True/False. Level-order traversal means visit the nodes at each level, one level
at at time, starting with the root.
True/False. In the computational strategy to implement a tree with an array, the
children of node n are stored at 2n + 1 and 2(n + 1) respectively.
What is a tree?
What is a node?
What is the root of the tree?
What is a leaf?
What is an internal node?
Define the height of a tree.
Define the level of a node.
6
What are the advantages and disadvantages of the computational strategy?
What attributes should be stored in the TreeNode class?
Which method of traversing a tree would result in a sorted list for a binary
search tree?
We used a list to implement the iterator methods for a binary tree. What must be
true for this strategy to be successful?