这是我为二叉搜索树编写的代码。不幸的是,当我运行它时,它没有给出所需的输出。有人可以告诉我我做错了什么吗?
import java.util.ArrayList;
public class BinaryOrderedTree {
BinaryOrderedTree left;
BinaryOrderedTree right;
static BinaryOrderedTree top;
int key;
static ArrayList<BinaryOrderedTree> values=new ArrayList<BinaryOrderedTree>();
public int getKey(){
return key;
}
public void setTop(BinaryOrderedTree top1){
top=top1;
}
public BinaryOrderedTree getLeft(){
return this.left;
}
public BinaryOrderedTree getRight(){
return this.right;
}
public BinaryOrderedTree(int key){
this.key=key;
}
public static BinaryOrderedTree addNode(BinaryOrderedTree node,BinaryOrderedTree top){
if (node.getKey()<top.getKey()){
if(top.left==null){
System.out.println(node.getKey());
System.out.println("left");
top.left=node;
}
else{
addNode(node,top.left);
}
}
if(node.getKey()>top.getKey()){
if(top.right==null){
System.out.println(node.getKey());
System.out.println("right");
top.right=node;
}
else{
addNode(node,top.right);
}
}
return node;
}
public static BinaryOrderedTree searchNode(BinaryOrderedTree search,
BinaryOrderedTree top){
if(search.getKey()==top.getKey()){
return top;
}
else if(search.getKey()<top.getKey()){
return searchNode(search,top.left);
}
else if(search.getKey()>top.getKey()){
return searchNode(search,top.right);
}
return null;
}
public static BinaryOrderedTree traverse(BinaryOrderedTree top){
values.add(top);
System.out.println(top.getKey());
if(top.left !=null)
traverse(top.left);
else if (top.right!=null)
traverse(top.right);
values.add(top.left);
values.add(top.right);
return top;
}
public static void main(String[] args){
BinaryOrderedTree top=new BinaryOrderedTree(7);
BinaryOrderedTree firstNode=new BinaryOrderedTree(6);
BinaryOrderedTree.addNode(firstNode,top);
BinaryOrderedTree secondNode=new BinaryOrderedTree(4);
BinaryOrderedTree.addNode(secondNode, top);
BinaryOrderedTree thirdNode=new BinaryOrderedTree(8);
BinaryOrderedTree.addNode(thirdNode, top);
BinaryOrderedTree fourthNode=new BinaryOrderedTree(3);
BinaryOrderedTree.addNode(fourthNode, top);
BinaryOrderedTree.traverse(top);
// System.out.println(BinaryOrderedTree.values);
}
}
This is the output I get
6
left
4
left
8
right
3
left
traversing pre-order
7
6
4
3
我只能假设节点已正确添加。但它无法显示顶部节点右侧的节点,仅遍历左侧部分。有人可以指出这个缺陷吗?
最佳答案
删除右侧遍历中的else
:
if(top.left !=null)
traverse(top.left);
if (top.right!=null)
traverse(top.right);
<小时/>
顺便说一句,您的值
也可能会被奇怪地填充。 values.add(top)
就足够了。删除那些 values.add(top.left)
和 values.add(top.right)
。
顺便说一句(还有一个)variable shadowing并不能真正帮助理解你的代码。
关于java - 用Java实现二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22046165/