时间戳

首页 > 解决方案 > 用于在 JavaScript 中的二叉树中插入节点的递归函数中的错误

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

问题描述

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

顺便说一句，我插入的值是 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);

标签： javascriptrecursionbinary-treeinsertion

解决方案

有这些问题：

  • 在if(!this.root){块中，您newNode在它收到值之前引用它，因此在此语句newNode 之前移动初始化。if

  • 在同一个块中你return this，但你写你想返回一个布尔值，所以把它改成return true;

  • 递归调用应该用于返回该调用返回的任何内容，因此请在它们前面加上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。此外，丰富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());

推荐阅读