首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >不对每个输入进行排序的二进制搜索树添加方法- JavaScript

不对每个输入进行排序的二进制搜索树添加方法- JavaScript
EN

Stack Overflow用户
提问于 2018-09-23 00:36:23
回答 1查看 112关注 0票数 2

我正在处理一个二进制搜索树,在向树中添加值时遇到了一个问题。当我按顺序(降序或升序)添加值(数字)时,它们会被添加到正确的位置,但如果我添加的值应该位于已在树中的值之间的某个位置,则它们不会排序。您可以看到,在图片中,数字3添加在1之后,但它应该在4和1之间,所以问题是,我到底做错了什么,以及如何修复它

我将在图片下方添加add函数的代码

Node对象

代码语言:javascript
复制
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函数

代码语言:javascript
复制
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)的输出;

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-09-23 02:18:51

3应该在右侧,因为它比1大。在您的输出中,这是正确的。在你的图片中,你在那里犯了一个错误。

除此之外,你的树很好。1小于3的事实是正确的,但BST只保证按顺序的树遍历生成树数据的排序列表,而不是保证树中每个较小的值都比较大的值更低。如果您执行按顺序树遍历,那么您的BST会给出1, 3, 4, 7, 8, 15

如果您不知道如何进行按顺序的树遍历,请查看以下内容:

来自Wikipedia

当节点底部的点被触摸时,只需注意每个数据。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52458676

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档