javascript - JavaScript 二叉搜索树按顺序遍历返回未定义作为答案的一部分

Question

我正在为 JS 中的 BST 编写递归中序遍历方法。该方法应该在数组中按顺序返回数值叶值。到目前为止，我的书面方法就是这样做的。但除了中序号之外，它还在我的数组末尾返回 3 'undefined'。我的 in order 方法的代码在这里：

this.inorder = function(){
        let travArr = [];

        function recurTrav(node){
            if(node.left == null && node.right == null){
                console.log("leaf: " + node.value);
                return node.value;
            }
            else if(node.right == null){
                console.log("right is null, val: " + node.value);
                travArr.push(recurTrav(node.left));
                travArr.push(node.value);
            }
            else if(node.left == null){
                console.log("left is null, val:" + node.value);
                travArr.push(node.value);
                travArr.push(recurTrav(node.right));
            }
            else{
                console.log("no nulls:");
                travArr.push(recurTrav(node.left));
                travArr.push(node.value);
                travArr.push(recurTrav(node.right));
            }
        }

        recurTrav(this.root);
        return travArr;
}

this.root 是 BST 的根节点。为简单起见，我有一个未在此处包含的 add 方法。节点具有 value、left 和 right 属性。

如果我按顺序将数字 3、2、5、6、14、8 添加到我的 BST 中，我的.inorder()方法会[2, 3, 5, 6, 8, 14, undefined, undefined, undefined]由于某种原因返回。我无法弄清楚这 3 个未定义的来自哪里。我认为这可能是因为我的 travArr.push()，它可能会返回“未定义”。

我意识到我可能只是做一些数组操作来删除那些“未定义”，但我真的很想了解我最初是如何编写错误的代码的。如果包含我的 BST 的完整代码更容易，请告诉我，我会包含它。

标签： javascriptrecursiondata-structures

Answer 1

你可以看看这部分：

function recurTrav(node) {
    if (node.left == null && node.right == null){
        console.log("leaf: " + node.value);
        return node.value;                                 // returns a value
    } else if(node.right == null){
        console.log("right is null, val: " + node.value);
        travArr.push(recurTrav(node.left));                // <------ could take undefined
        travArr.push(node.value);                          // no return until end of funct
    }
    //..
    // missing return, takes default return value.
}

解决方案：仅在必要时推送并调用函数，而不使用结果进行推送。

function recurTrav(node) {
    if (!node.left && !node.right) {                      // falsy check incl undefined/null
        console.log("leaf: " + node.value);
        travArr.push(node.value);
        return;                                           // omit else parts
    }                                                     // with early returns
    if (!node.right) {
        console.log("right is null, val: " + node.value);
        recurTrav(node.left);
        travArr.push(node.value);
        return;
    }
    if (!node.left) {
        console.log("left is null, val:" + node.value);
        travArr.push(node.value);
        recurTrav(node.right);
        return;
    }
    console.log("no nulls:");
    recurTrav(node.left);
    travArr.push(node.value);
    recurTrav(node.right);
}