BST遍历预序
BST traversal pre-order
在 BST 前序遍历中,我没有看到预期的结果。
请帮忙确认是代码的问题还是我对预序遍历的理解有问题
节点:
class node implements Comparable<node>{
int v;
node left;
node right;
node(int v){ this.v=v;}
boolean equals(node o){
return(this.v==o.v);
}
@Override public int compareTo(node aThat) {
return this.v<aThat.v?-1:this.v>aThat.v?1:0;
}
public String toString(){ return "->" + this.v;}
}
插入代码 -
public binarySearch(int r){
Random rnd=new Random();
int[] val=new int[r];
for(int i=0;i<r;i++){
val[i]=rnd.nextInt(50);
}
System.out.println("Array -> " + Arrays.toString(val));
root=new node(val[0]);
for(int i=1;i<val.length-1;i++){
insert(root,new node(val[i]));
}
}
插入(构建)代码 -
private void insert(node curr,node c){
if(curr==c){ return;}
if(curr.compareTo(c)<0)
{
if(curr.left==null){curr.left=c; return;}
insert(curr.left,c);
}
else
{
if(curr.right==null){curr.right=c; return;}
insert(curr.right,c);
}
}
遍历码(预购)-
private void print(node c){
if(c==null) return;
System.out.println(c);
print(c.left);
print(c.right);
}
输入数组 -
[22, 17, 24, 11, 5, 9, 25]
预期(?)-
->22 ->17 ->11 ->5 ->9 ->24
输出 -
->22 ->24 ->17 ->11 ->5 ->9
您正在使用 curr.compareTo(c)<0
(意思是“c
比 curr
大 ”)作为放置 c
的条件] 在 curr
的 左边 。我不确定你到底想写什么,但它恰恰与此相反。 (要么翻转c
和curr
,要么把<
改成>
,要么左右互换。)
在 BST 前序遍历中,我没有看到预期的结果。
请帮忙确认是代码的问题还是我对预序遍历的理解有问题
节点:
class node implements Comparable<node>{
int v;
node left;
node right;
node(int v){ this.v=v;}
boolean equals(node o){
return(this.v==o.v);
}
@Override public int compareTo(node aThat) {
return this.v<aThat.v?-1:this.v>aThat.v?1:0;
}
public String toString(){ return "->" + this.v;}
}
插入代码 -
public binarySearch(int r){
Random rnd=new Random();
int[] val=new int[r];
for(int i=0;i<r;i++){
val[i]=rnd.nextInt(50);
}
System.out.println("Array -> " + Arrays.toString(val));
root=new node(val[0]);
for(int i=1;i<val.length-1;i++){
insert(root,new node(val[i]));
}
}
插入(构建)代码 -
private void insert(node curr,node c){
if(curr==c){ return;}
if(curr.compareTo(c)<0)
{
if(curr.left==null){curr.left=c; return;}
insert(curr.left,c);
}
else
{
if(curr.right==null){curr.right=c; return;}
insert(curr.right,c);
}
}
遍历码(预购)-
private void print(node c){
if(c==null) return;
System.out.println(c);
print(c.left);
print(c.right);
}
输入数组 -
[22, 17, 24, 11, 5, 9, 25]
预期(?)-
->22 ->17 ->11 ->5 ->9 ->24
输出 -
->22 ->24 ->17 ->11 ->5 ->9
您正在使用 curr.compareTo(c)<0
(意思是“c
比 curr
大 ”)作为放置 c
的条件] 在 curr
的 左边 。我不确定你到底想写什么,但它恰恰与此相反。 (要么翻转c
和curr
,要么把<
改成>
,要么左右互换。)