为什么在尝试搜索二叉树时出现无限循环？

Question

我在树中插入了数字。我使用 get 来查看该数字是否存在（知道它存在）并且 google chrome 崩溃，因为它无限循环。我已经多次查看代码，但无法弄清楚为什么它不起作用。请帮忙。

我在控制台中的命令：

 tree = new BinaryTree;

 tree.insert(15);
 tree.insert(23);
 tree.insert(6);

等...

 tree.get(55);

Google Chrome 崩溃 NOOOOOO 崩溃

class Node {
    constructor(val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    constructor(){
        this.root = null;
    }

    insert(val){
        var newNode = new Node(val);
        if (this.root){
            var current = this.root
            while(true) {
            if(val < current.val){
                if(current.left === null){
                    current.left = newNode;
                    return current;
                }
                current = current.left;
            }
            if(val > current.val){
                if(current.right === null){
                    current.right = newNode;
                    return current; 
                }
                current = current.right;
            }
            if(val === current.val){
                return "already exists";
            }
        }
    }
    this.root = newNode;
    return this;
}

    get(val) {

        if(this.root){
            var current = this.root;
            while(true){
                if (val < current.val){
                    if(current.left == null){
                        return "does not exist";
                    }
                    current = current.left;
                }
                if (val > current.val){
                    if(current.right == null){
                        return "does not exist";
                    }
                    current = current.right;
                }
                 if(current === val){
                        return current;
               } 
            }
        }
        return "tree is empty";
    }
}

Answer 1

您的代码永远不会跳出此 while 循环

 while(true) {
   if(val < current.val){
      if(current.left === null){
         current.left = newNode;
         return current;
       }
      current = current.left;
   }
 }

white(true) 将永远为真，因此如果您不 return 退出循环，它将无限运行，所以我的猜测是出于某种原因 current.left === null 永远不会是真的

Answer 2

您的代码很好，您只是简单地在 get() 方法底部进行了相等性检查错误。您正在检查节点对象本身是否与传入的值相等，而不是 .val 属性.

您写道：

if(current === val){
    return current;
}

何时需要：

if(current.val === val){
    return current;
}

为什么在尝试搜索二叉树时出现无限循环？

Why am I getting an infinite loop while trying to search my Binary Tree?

javascript

binary-tree