DST, Tutorial#3. 3. maxDepth() Solution (Java). 4. minValue() Solution (Java). 9. mirror() Solution (Java). 11. sameTree() Solution (Java)

DST, Tutorial#3

Java

3. maxDepth() Solution (Java)

/**
Returns the max root-to-leaf depth of the tree.
Uses a recursive helper that recurs down to find
the max depth.
*/
public int maxDepth() {
return(maxDepth(root));
}

private int maxDepth(Node node) {
if (node==null) {
return(0);
}
else {
int lDepth = maxDepth(node. left);
int rDepth = maxDepth(node. right);

// use the larger + 1
return(Math. max(lDepth, rDepth) + 1);
}
}

4. minValue() Solution (Java)

/**
Returns the min value in a non-empty binary search tree.
Uses a helper method that iterates to the left to find
the min value.
*/
public int minValue() {
return( minValue(root) );
}

/**
Finds the min value in a non-empty binary search tree.
*/
private int minValue(Node node) {
Node current = node;
while (current. left! = null) {
current = current. left;
}

return(current. data);
}

9. mirror() Solution (Java)

/**
Changes the tree into its mirror image.

So the tree...
4
/ \
2 5
/ \
1 3

is changed to...
4
/ \
5 2
/ \
3 1

Uses a recursive helper that recurs over the tree,
swapping the left/right pointers.
*/
public void mirror() {
mirror(root);
}

private void mirror(Node node) {
if (node! = null) {
// do the sub-trees
mirror(node. left);
mirror(node. right);

// swap the left/right pointers
Node temp = node. left;
node. left = node. right;
node. right = temp;
}
}

11. sameTree() Solution (Java)

/*
Compares the receiver to another tree to
see if they are structurally identical.
*/
public boolean sameTree(BinaryTree other) {
return( sameTree(root, other. root) );
}

/**
Recursive helper -- recurs down two trees in parallel,
checking to see if they are identical.
*/
boolean sameTree(Node a, Node b) {
// 1. both empty -> true
if (a==null & & b==null) return(true);

// 2. both non-empty -> compare them
else if (a! =null & & b! =null) {
return(
a. data == b. data & &
sameTree(a. left, b. left) & &
sameTree(a. right, b. right)
);
}
// 3. one empty, one not -> false
else return(false);
}

Problem: You are given a set of phone numbers and the names of people to whom they belong. You are to create a binary search tree to quickly look up people based on their phone numbers. What sort of data will you put into the nodes and by what piece of the data will the tree be ordered?

You will need a structure that contains a name. A char * to hold a string will work. To hold the phone number, a character array of size 7 will work nicely (if you needed area codes too, then you would need 10 characters). The sorting in the binary search tree should be based on this second data element, the phone number, since we are going to be accessing (searching) the information based on phone number.

12 3 Следующая ⇒