JavaScript 中用于在二叉树中插入节点的递归函数错误

Question

我在树中插入节点后变得未定义，不知道为什么会这样。这是正在发生的事情 - 插入节点后，该函数应该 return 为真，但它 return 未定义。插入节点后，代码不会停止并返回到if检查条件，将'current'设置为'7'，这种情况一直发生直到'current'为'10'（根值）然后它最后回到 return 未定义的 insert() 函数。我唯一的问题是，为什么它 returning 未定义，为什么在将节点插入所需位置后又回到根目录。有人可以告诉我吗？我是不是遗漏了一些很小的东西？

对了，我插入的值是8。tree.insert(8);

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

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

    insert(val){
        if(!this.root){
          this.root = newNode;
          return this;
        }
        let newNode = new Node(val);
        if(val === this.root.val)return false;
     
        function recursiveInsert(current,newNode){ 
            if(newNode.val === current.val)return false;      

            if(newNode.val > current.val){
              if(!current.right){
                  current.right = newNode;             
                  return true;
              }           
              recursiveInsert(current.right,newNode);
            }

            if(newNode.val<current.val){   
              if(!current.left){
                  current.left = newNode;              
                  return true;
            }
            recursiveInsert(current.left, newNode);
          }        
       }    
      return recursiveInsert(this.root,newNode);                         
    }
  }

let tree = new BinarySearchTree();

tree.root = new Node(10);
tree.root.left = new Node(7);
tree.root.right = new Node(15);
tree.root.left.right = new Node(9);

Answer 1

存在这些问题：

在 if(!this.root){ 块中，您在 newNode 收到值之前引用 newNode，因此将 newNode 的初始化移动到 before 这个 if 语句。
在你 return this 的同一块中，但你写了你想要 return 一个布尔值，所以将其更改为 return true;
递归调用应该用于 return 无论调用什么 returned，因此在它们前面加上 return，就像您在最后一行进行初始调用时所做的那样。

演示

我还建议使用 insert 方法构建初始树。并添加一个迭代器，以便您可以按顺序快速输出树。

请注意，有一个 else if 条件始终为真，因此只需使用 else:

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
    // Add this method for inorder traversal of the values
    * inorder() {
        if (this.left) yield * this.left.inorder();
        yield this.val;
        if (this.right) yield * this.right.inorder();
    }
}

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

    insert(val) {
        let newNode = new Node(val); // First create the node
        if (!this.root) {
            this.root = newNode;
            return true; // you wanted a boolean
        }
        // This is not necessary: it already happens in the function below
        //         if(val === this.root.val)return false;
     
        function recursiveInsert(current,newNode) { 
            if (newNode.val === current.val) return false;      

            if (newNode.val > current.val) {
                if (!current.right) {
                    current.right = newNode;             
                    return true;
                }
                // Return the result
                return recursiveInsert(current.right, newNode);
            } else { // it is the only possibility left
                if (!current.left) {
                    current.left = newNode;              
                    return true;
                }
                // Return the result
                return recursiveInsert(current.left, newNode);
            }        
        }
        
        return recursiveInsert(this.root, newNode);                         
    }
}

let tree = new BinarySearchTree();

// Build the tree only with the insert-method
tree.insert(10);
tree.insert(7);
tree.insert(15);
tree.insert(9);

tree.insert(8); // Add the value you wanted to test with
tree.insert(15); // Try some duplicate

console.log(...tree.root.inorder());

您可以通过使递归插入函数成为 Node class 的方法来使代码更好一些。此外，丰富 BinarySearchTree 构造函数，以便它可以获得许多值作为开始，就像本机 Array 构造函数一样。

class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
    
    * inorder() {
        if (this.left) yield * this.left.inorder();
        yield this.val;
        if (this.right) yield * this.right.inorder();
    }
    
    insert(val) { 
        if (val === this.val) return false;      

        if (val > this.val) {
            if (this.right) return this.right.insert(val);
            this.right = new Node(val); 
        } else {
            if (this.left) return this.left.insert(val);
            this.left = new Node(val);             
        }        
        return true;
    }
}

class BinarySearchTree {
    constructor(...values) {
        this.root = null;
        for (let val of values) this.insert(val);
    }

    * inorder() {
        if (this.root) yield * this.root.inorder();
    }

    insert(val) {
        if (this.root) return this.root.insert(val);
        this.root = new Node(val);
        return true;
    }
    
    
}

let tree = new BinarySearchTree(10, 7, 15, 9);
tree.insert(8);
tree.insert(15);

console.log(...tree.inorder());

Answer 2

你应该 return recursiveCall 否则你会得到 undefined 因为递归调用需要时间来执行并且函数不会等待它 return 东西。

// ...code
return recursiveInsert(current.right,newNode);
// and
return recursiveInsert(current.left,newNode);

JavaScript 中用于在二叉树中插入节点的递归函数错误

Error in Recursive Function Used For Inserting a Node in a Binary Tree in JavaScript

javascript

recursion

binary-tree

insertion

演示