我正在处理一个二进制搜索树,在向树中添加值时遇到了一个问题。当我按顺序(降序或升序)添加值(数字)时,它们会被添加到正确的位置,但如果我添加的值应该位于已在树中的值之间的某个位置,则它们不会排序。您可以看到,在图片中,数字3添加在1之后,但它应该在4和1之间,所以问题是,我到底做错了什么,以及如何修复它
我将在图片下方添加add函数的代码
Node对象
function Node(data){
this.data=data;
this.left=null;
this.right=null;}
function BinarySearchTree(){
this.root = null;
var current=null;
var newNode=null;
this.add = function(data){
var root = this.root;
if(!root){
this.root= new Node(data);
return;
}else{
if(this.ifExists(data)){
}else{
current=root;
newNode= new Node(data);
while(current){
if(data<current.data){
if(!current.left){
current.left=newNode;
break;
}else{
current= current.left;
}
}else{
if(!current.right){
current.right=newNode;
break;
}else{
current=current.right;
}
}
}
}
}
}
}
this.ifExists=function(data){
var current = this.root;
// console.log(current);
while(current){
if(data==current.data){
return true;
}
current = data < current.value ? current.left : current.right;
}
return false;
}
}
如何调用add函数
var bst= new BinarySearchTree();
bst.add(7);
bst.add(8);
bst.add(4);
bst.add(1);
bst.add(15);
bst.add(67);
bst.add(9);
bst.add(3);
console.log(bst);
Console.log(Bst)的输出;
发布于 2018-09-23 02:18:51
3
应该在右侧,因为它比1
大。在您的输出中,这是正确的。在你的图片中,你在那里犯了一个错误。
除此之外,你的树很好。1小于3的事实是正确的,但BST只保证按顺序的树遍历生成树数据的排序列表,而不是保证树中每个较小的值都比较大的值更低。如果您执行按顺序树遍历,那么您的BST会给出1, 3, 4, 7, 8, 15
如果您不知道如何进行按顺序的树遍历,请查看以下内容:
当节点底部的点被触摸时,只需注意每个数据。
https://stackoverflow.com/questions/52458676
复制相似问题