我建议考虑尾递归,因为从性能角度来看,这是一个重要因素:
public static Node getNode(Node currentNode, String name){
if (currentNode == null) {
return null;
}
Node retrieved = null;
if (currentNode.name.equals(name)) {
return currentNode;
} else {
if(currentNode.left == null) {
return getNode(currentNode.right, name);
}
else if(currentNode.right == null) {
return getNode(currentNode.left, name);
}
else {
retrieved = getNode(currentNode.left, name);
if (retrieved == null){
retrieved = getNode(currentNode.right, name);
}
}
}
return retrieved;
}
附上完整的代码,该代码已在在线编译器上执行:
public class MyClass {
static class Node {
public String name;
public Node left;
public Node right;
Node(String name) {
this.name = name;
right = null;
left = null;
}
@Override
public String toString() {
return "name = " + name + " hasLeft = " + (left != null) + " hasRight = " + (right != null);
}
}
static class Tree {
Node root;
public Node getRoot() {
return root;
}
private Node addRecursive(Node current, String value) {
if (current == null) {
return new Node(value);
}
if (value.compareTo(current.name) < 0) {
current.left = addRecursive(current.left, value);
} else if (value.compareTo(current.name) > 0) {
current.right = addRecursive(current.right, value);
} else {
return current;
}
return current;
}
public Tree add(String value) {
root = addRecursive(root, value);
return this;
}
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.name);
traverseInOrder(node.right);
}
}
public void traverseInOrder() {
traverseInOrder(root);
System.out.println("");
}
}
public static void main(String args[]) {
Tree tree = new Tree();
tree.add("a").add("ab").add("bbb").add("cc").add("zolko").add("polip").traverseInOrder();
Node found = getNode(tree.getRoot(),"vv");
System.out.println(found);
found = getNode(tree.getRoot(),"ab");
System.out.println(found);
found = getNode(tree.getRoot(),"polip");
System.out.println(found);
found = getNode(tree.getRoot(),"java");
System.out.println(found);
found = getNode(tree.getRoot(),"zolko");
System.out.println(found);
}
public static Node getNode(Node currentNode, String name){
if (currentNode == null) {
return null;
}
Node retrieved = null;
if (currentNode.name.equals(name)) {
return currentNode;
} else {
if(currentNode.left == null) {
return getNode(currentNode.right, name);
}
else if(currentNode.right == null) {
return getNode(currentNode.left, name);
}
else {
retrieved = getNode(currentNode.left, name);
if (retrieved == null){
retrieved = getNode(currentNode.right, name);
}
}
}
return retrieved;
}
}
主方法执行的输出:
a ab bbb cc polip zolko
null
name = ab hasLeft = false hasRight = true
name = polip hasLeft = false hasRight = false
null
name = zolko hasLeft = true hasRight = false