Binary Tree

In a binary tree, the branches go only from a child to a parent.

F.

In a binary tree, the branches go only from parent to its children.

The level of the root node of a binary tree is 1.

F.

The level of the root node of a binary tree is 0.

All binary tree traversals start at the left-most child node.

F.

All binary tree traversals start at the root node.

The item search, insertion, and deletion operations all require the binary tree to be traversed.

T.

For classes with pointer data members, you must explicitly overload the assignment operator and include the destructor.

T.

The operations to do inorder, preorder, and postorder traversals of a binary search tree are the same as those for a binary tree.

T.

Duplicates are allowed in a binary search tree.

F.

All keys in left-sub tree of a key must be smaller and all keys in right-sub tree must be greater.

After deleting the desired item from a binary search tree, the resulting tree must be a binary search tree

T.

To delete an item from the binary search tree, you must do the following:

1. Find the node containing the item (if any) to be deleted.

2. Delete the node.

T.

In C++, a function name without any parentheses is considered a pointer to the function.

T.

1. In the diagram of a binary tree, an arrow is called a(n) ____.

a. relation

b. path

c. directed line

d. directed branch

D. directed branch

2. A binary tree has a special node called the ____ node.

a. super

b. root

c. superparent

d. rootleaf

B. root

In a diagram of a binary tree, each node is represented as a(n) ____.

a. line

b. triangle

c. circle

d. rectangle

C. circle

In copying a binary tree, if you use just the value of the pointer of the root node, you get a ____ copy of the data.

a. static

b. shallow

c. deep

d. local

B. shallow

The most common operation performed on a binary tree is a(n) ____.

a. insertion

b. deletion

c. search

d. traversal

D. traversal

The three traversal algorithms discussed for binary trees are ____, ____, and ____.

a. order, preorder, postorder

b. in, preorder, order

c. order, preorder, post

d. inorder, preorder, postorder

D. inorder, preorder, postorder

16. The listing of the nodes produced by the postorder traversal of a binary tree is called the ____.

a. postsequence

b. postorder sequence

c. postorder table

d. post-script

B. postorder sequence

17. The sequence of operations in a postorder traversal is ____.

a. traverse left; traverse right

b. traverse left; traverse right; visit

c. visit; traverse left; traverse right

d. traverse left; visit; traverse right

B. traverse left; traverse right; visit

18. A binary tree is also a(n) ____.

a. stack

b. linked list

c. graph

d. array

C. graph

19. A binary tree is empty if root is ____.

a. 0

b. 1

c. "zero"

d. NULL

D. NULL

20. Assume the key of the left child below the root node of a binary search tree is 30. The value in the root node could be ____.

a. 0

b. 10

c. 30

d. 40

D. 40

The key of the right child below the root node of a search binary tree is 40. The value in the root node could be ____.

a. 30

b. 40

c. 50

d. 60

A. 30

22. In a binary search tree, the data in each node is ____ the data in the left child.

a. larger than

b. smaller than

c. equal to

d. larger or equal to

A. larger than

In a binary search tree, the data in each node is ____ the data in the right child.

a. equal to

b. smaller than

c. greater than

d. smaller or equal to

B. smaller than

The search function searches the binary search tree for a given item. If the item is found in the binary search tree, it returns ____.

a. true

b. false

c. a reference to the node where the item was found

d. 1

A. true

When traversing a binary tree with the pointer current, the pointer current is initialized to ____.

a. NULL

b. llink

c. rlink

d. root

D. root

The ____________________ of a path in a binary tree is the number of branches on that path.

lenght

The ____________________ of a binary tree is the number of nodes on the longest path from the root to a leaf.

height

In a(n) ____________________ traversal, the binary tree is traversed as follows:

1. Traverse the left subtree

2. Visit the node

3. Traverse the right subtree

inorder

In a(n) ____________________ traversal, the binary tree is traversed as follows:

1. Visit the node.

2. Traverse the left subtree.

3. Traverse the right subtree.

preorder

The listing of the nodes produced by the preorder traversal of a binary tree is called the ____________________.

preorder sequence

The listing of the nodes produced by the inorder traversal of a binary tree is called the ____________________.

inorder sequence

In addition to the inorder, preorder, and postorder traversals, a binary tree can also be traversed level-bylevel, which is also known as ____________________ traversal.

breadth-first

To destroy a binary tree, for each node, first we destroy its left subtree, then its right subtree, and then the node itself. We must then use the operator ____________________ to deallocate the memory occupied by the node.

delete

When a class object is passed by value, the ____________________ constructor copies the value of the actual parameters into the formal parameters.

copy

After inserting an item in a binary search tree, the resulting binary tree must be a(n) ____________________.

binary search tree

Let T be a binary search tree with n nodes, in which n > 0. When T is linear, the search algorithm makes ____________________ key comparisons, in the unsuccessful case.

n

Let T be a binary search tree with n nodes, in which n > 0. The average number of nodes visited in a search of T is approximately O(____________________).

log2n