Java Reference
In-Depth Information
while ((cmp = d.compareTo(curr.data)) != 0) {
if (cmp < 0) { //try left
if (curr.left == null) {
curr.left = new TreeNode(d);
curr.left.parent = curr;
return curr.left;
}
curr = curr.left;
}
else { //try right
if (curr.right == null) {
curr.right = new TreeNode(d);
curr.right.parent = curr;
return curr.right;
}
curr = curr.right;
} //end else
} //end while
return curr; //d is in the tree; return pointer to the node
} //end findOrInsert
When we need to add a node ( N , say) to the tree, if curr points to the node from which the new node will hang, we
simply set the parent field of N to curr .
We can test findOrInsert and inOrderTraversal with Program P8.3.
Program P8.3
import java.io.*;
import java.util.*;
public class P8_3BinarySearchTreeTest {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("words.in"));
BinaryTree bst = new BinaryTree();
in.useDelimiter("[^a-zA-Z]+");
while (in.hasNext()) {
String word = in.next().toLowerCase();
TreeNode node = bst.findOrInsert(new NodeData(word));
}
System.out.printf("\n\nThe in-order traversal is: ");
bst.inOrderTraversal();
System.out.printf("\n");
in.close();
} // end main
} //end class P8_3BinarySearchTreeTest
Search WWH ::




Custom Search