Short Answers Section 9.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 9.2
Tree
Representations
Short Answers
Section 9.3
A Toolkit for
Binary Tree Nodes
public static void subswap(BTNode root) // Precondition: Root is the root reference of a binary tree. // Postcondition: If root is non-null, then the original left subtree below // this root 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
public static void flip(BTNode root) // Precondition: Root is the root reference of a binary tree. // Postcondition: If the root is non-null, then the tree below this node 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 9.4 Tree Traversals |
14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40Write the order of the nodes visited in:
public static void increase(IntBTNode root) // Precondition: root is the root reference of a binary tree. // Postcondition: Every node of the tree has had its data // increased by one.
public static int manyNodes(BTNode root) // Precondition: root_ptr is the root reference 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.
public static int treeDepth(BTNode root) // Precondition: root_ptr is the root reference 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.
public static int count42(IntBTNode root) // Precondition: root is the root reference 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 method returns zero.
public static boolean has42(IntBTNode root) // Precondition: root is the root reference 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 method returns false.
public static boolean all42(IntBTNode root) // Precondition: root is the root reference 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 method returns true.
public static int sum(IntBTNode root) // Precondition: root is the root reference 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 9.5
Binary Search
Trees
public static int count42(BTNode root) // Precondition: root is the root reference of a binary SEARCH tree. // Postcondition: The return value indicates how many times 42 appears // in the tree.
public static int max(BTNode root) // Precondition: root is the root reference of a nonempty binary SEARCH // tree. // Postcondition: The return value is the largest value in the tree.
void insert42(BTNode root) // Precondition: root is the root reference of a binary SEARCH tree. // Postcondition: One copy of the number 42 has been added to the binary // search tree.
Multiple Choice Section 9.1 Introduction to Trees |
14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40 |
Multiple Choice
Section 9.2
Tree
Representations
Multiple Choice
Section 9.3
A Toolkit for
Binary Tree Nodes
Multiple Choice
Section 9.4
Tree
Traversals
14
/ \
2 11
/ \ / \
1 3 10 30
/ /
7 40
Multiple Choice
Section 9.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?