Exercises:
C-7.3:
Design algorithms for the following operations for a binary tree T:
preorderNext(v): return the node visited after node v in a preorder traversal of T
inorderNext(v): return the node visited after node v in an inorder traversal of T
postorderNext(v): return the node visited after node v in a postorder traversal of T.
What are the worst-case running times of your algorithms?
preorderNext(v):
Algorithm preorderNext(Node v):
if v isInternal() then
return v’s left child
else
Node p = parent of v
if v is left child of p then
return right child of p
else
while v is not left child of p do
v = p
p = p.parent
return right child of p
inorderNext(v):
Algorithm inorderNext(Node v):
if v isInternal() then
v = right child of v
while v is not external do
v = left child of v
return v
else
Node p = parent of v
if v is left child of p then
return p
else
while v is not left child of p do
v = p
p = p.parent
return p
11 Data Structures and Algorithms Discussion
postorderNext(v):
Algorithm postorderNext(Node v):
if v isInternal() then
p = parent of v
if v = right child of p then
return p
else
v = right child of p
while v is not external do
v = left child of v
return v
else
p = parent of v
if v is left child of p then
return right child of p
else
return p
Write a comparator for nonnegative integers that determines order based on the number of 1’s in each
integer’s binary expansion, so that i < j if the number of 1’s in the binary representation of i is less
than the number of 1’s in the binary representation of j.
Answer
import java.util.Comparator;
public class integerComparator implements Comparator {
private int countBits(Object a) {
if( a == null ) {
throw new RuntimeException("Null Argument");
}
try{
int numOnes = 0;
int tmp = ((Integer) a).intValue();
while( tmp != 0 ) {
int bit = tmp & 1;
if( bit...
