Short Answers Section 10.1 Introduction to Trees |
14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40Circle all the leaves. Put a square box around the root. Draw a star around each ancestor of the node that contains 10. Put a big X through every descendant of the node the contains 10.
Short Answers
Section 10.2
Tree
Representations
Short Answers
Section 10.3
A Toolkit for
Binary Tree Nodes
template <class Item> void subswap(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a non-empty binary tree. // Postcondition: The original left subtree has been moved and is now the right // subtree, and the original right subtree is now the left subtree. // Example original tree: Example new tree: // 1 1 // / \ / \ // 2 3 3 2 // / \ / \ // 4 5 4 5
template <class Item> void flip(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a non-empty binary tree. // Postcondition: The tree is now the mirror image of its original value. // Example original tree: Example new tree: // 1 1 // / \ / \ // 2 3 3 2 // / \ / \ // 4 5 5 4
Short Answers
Section 10.4
Tree
Traversals
14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40Write the order of the nodes visited in:
template <class Item> void increase(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree. // Postcondition: Every node of the tree has had its data increased by one.
template <class Item> size_t many_nodes(binary_tree_node< Item> * root_ptr) // Precondition: root_ptr is the root pointer of a binary tree. // Postcondition: The return value is the number of nodes in the tree. // NOTES: The empty tree has 0 nodes, and a tree with just a root has // 1 node.
template <class Item> int tree_depth(binary_tree_node< Item> * root_ptr) // Precondition: root_ptr is the root pointer of a binary tree. // Postcondition: The return value is the depth of the binary tree. // NOTES: The empty tree has a depth of -1 and a tree with just a root // has a depth of 0.
template <class Item> size_t count42(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (but // NOT NECESSARILY a search tree). // Postcondition: The return value indicates how many times 42 appears // in the tree. NOTE: If the tree is empty, the function returns zero.
template <class Item> bool has_42(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (but // NOT NECESSARILY a search tree). // Postcondition: The return value indicates whether 42 appears somewhere // in the tree. NOTE: If the tree is empty, the function returns false.
template <class Item> bool all_42(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree (but // NOT NECESSARILY a search tree). // Postcondition: The return value is true if every node in the tree // contains 42. NOTE: If the tree is empty, the function returns true.
template <class Item> int sum_all(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a binary tree. // Postcondition: The return value is the sum of all the data in all the nodes. // NOTES: The return value for the empty tree is zero.
Short Answers
Section 10.5
Binary Search
Trees
template <class Item> size_t count42(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a binary SEARCH tree. // Postcondition: The return value indicates how many times 42 appears // in the tree.
template <class Item> int max(binary_tree_node<Item>* root_ptr) // Precondition: root_ptr is the root pointer of a nonempty binary SEARCH // tree. // Postcondition: The return value is the largest value in the tree.
template <class Item> void insert_one_42(binary_tree_node<Item>*&root_ptr) // Precondition: root_ptr is the root pointer of a binary SEARCH tree. // Postcondition: One copy of the number 42 has been added to the binary // search tree.
Multiple Choice Section 10.1 Introduction to Trees |
14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40 |
Multiple Choice
Section 10.2
Tree
Representations
Multiple Choice
Section 10.3
A Toolkit for
Binary Tree Nodes
Multiple Choice
Section 10.4
Tree
Traversals
14
/ \
2 11
/ \ / \
1 3 10 30
/ /
7 40
Multiple Choice
Section 10.5
Binary Search
Trees
14 / \ 2 16 / \ 1 5 / 4Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?
Data Structures and Other Objects Using C++
Thank you for visiting
http://www.cs.colorado.edu/~main/questions/chap10q.html
Copyright © 2000
Addison-Wesley Computer and Engineering Publishing Group