我正在尝试使用中序遍历来实现二叉搜索树。我正在尝试依次打印一系列数字来测试它。看起来它排序得很好,但有时会打印重复的数字。看看我的代码的相关部分:
树类和方法:
public class Tree {
Node root;
public Tree(){
root = null;
}
public Node add(Node n, int value){
if(n== null){
n= new Node(value);
}else if(value < n.getValue()){
n.addLeftNode(add(n.getLeft(),value));
}else if(value > n.getValue()){
n.addRightNode(add(n.getRight(),value));
}
return n;
}
public static Node traverse(Node n){
Node result = new Node();
if(n != null){
if(n.getLeft() != null){
result = traverse(n.getLeft());
System.out.println(result.getValue());
}
result = n;
System.out.println(result.getValue());
if(n.getRight() != null){
result = traverse(n.getRight());
System.out.println(result.getValue());
}
}
return result;
}
}
这就是它打印出来的内容:
<小时/>0 0 1 1 3 4 4 5 6 7 7 8 10 11 12 12 12 15 15 15 15 15 15 15 16 18 18 20 21 22 22 22 22 23 27 28 28 28 29 34 35 43 43 43 43 43 43 43 44 45 45 55 56 59 66 75 75 75 75 75 75 76 76 76 78 88 89 89 90 90 90 98 98
有什么线索吗?我猜这与遍历有关。尝试调试它,但我仍然找不到问题。如您所见,编号至少已排序。
最佳答案
当你向左或向右遍历时,调用 traverse 将打印左/右节点。您不必分别打印左侧和右侧。
if(n != null){
if(n.getLeft() != null){
result = traverse(n.getLeft());
// System.out.println(result.getValue());
}
result = n;
System.out.println(result.getValue()); // This prints the left and right via recursion into traverse(...)
if(n.getRight() != null){
result = traverse(n.getRight());
// System.out.println(result.getValue());
}
}
关于java - 二叉树遍历的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16269085/