javascript - 递归连接传递的字符串

Question

我正在用 JS 编写 BST，并尝试将传递给成员函数的字符串连接起来但没有成功。console.log()有效，但它会自动为每个条目开始一个新行。

"use strict";

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

class BST {
    constructor() {
        this.root = null;
    }
    insert(parent, key) {
        if (!this.root) return this.root = new Node(key);
        else {
            if (key < parent.data) {
                if (!parent.left) {
                    parent.left = new Node(key);
                } else {
                    this.insert(parent.left, key);
                }
            } else if (key > parent.data) {
                if (!parent.right) {
                    parent.right = new Node(key);
                } else {
                    this.insert(parent.right, key);
                }
            }
        }
    }
    
    // Doesn't work
    printIN(parent, string) {
        if (parent) {
            this.printIN(parent.left);
            console.log(parent.data);
            string += " " + parent.data;
            // return string += " " + parent.data;
            this.printIN(parent.right);
        }
        return string;
    }
    
    // This works.
    // printIN(parent) {
    //     if (parent) {
    //         this.printIN(parent.left);
    //         console.log(parent.data);
    //         this.printIN(parent.right);
    //     }
    // }
}


let treeA = new BST();
let tree = null;

tree = treeA.insert(treeA.root, 5);
tree = treeA.insert(treeA.root, 7);
tree = treeA.insert(treeA.root, 3);
tree = treeA.insert(treeA.root, 14);


let string = [""];
string = treeA.printIN(treeA.root, string);
console.log();
console.log(string);

// treeA.printIN(treeA.root);

我想在一行上打印出数字，而不是每次都从新行开始。我认为使用字符串连接是合乎逻辑的解决方案，但我似乎无法使其工作。

    // Doesn't work
    printIN(parent, string) {
        if (parent) {
            this.printIN(parent.left);
            console.log(parent.data);
            string += " " + parent.data;
            // return string += " " + parent.data;
            this.printIN(parent.right);
        }
        return string;

标签： javascriptclassrecursion

Answer 1

另一个答案为您提供了字符串问题的解决方案。下面的代码片段有一个替代方案。但更重要的是，它为您的 OOP 方法提供了一些重要的清理。

有两个主要原因是必要的。

首先，您有对象的成员函数，它们仍然需要将对象传递给它们。这是多余和令人困惑的。任何不引用的 OOP 函数都this应该是静态函数。但是，如果您要进行 OOP（实际上我可能会反对），那么您不应该像使用方法一样使用静态函数。因此insert，printIN不应该有parent参数。

其次，您正在处理递归结构。树的节点应该与树本身具有相同的设计。这使各种事情变得更容易。但是你有一个类Node和一个叫BST. 然后BST有一个root节点，它应该是递归的。我看不出有什么理由。BST 本质上是一个根节点，具有一个data值（通常，尽管我们可以像您一样将其设为可选）并且可能left和right节点本身就是 BST。

将代码修复为像这样工作可以大大简化它。这是一种实现：

class BST {
    constructor(data) {
        this.data = data;
    }
  
    insert(key) {
        if (!this.data) {
            this.data = key;
        } else {
            if (key < this.data) {
                if (!this.left) {
                    this.left = new BST(key);
                } else {
                    this.left.insert(key);
                }
            } else if (key > this.data) {
                if (!this.right) {
                    this.right = new BST(key);
                } else {
                    this.right.insert(key);
                }
            }
        }
    }

    printIN() {
        return (this.left ? this.left.printIN() + ' ' : '') +
               this.data +
               (this.right ? ' ' + this.right.printIN() : ''); 
    }
}


let treeA = new BST();

treeA.insert(5);
treeA.insert(7);
treeA.insert(3);
treeA.insert(14);

console.log(treeA.printIN());

这里没有Node课。一切都在BST. 此外，BST对象不需要root节点，方法更简单。

我会注意到，尽管这printIN比我们可以以相同方式使用的另一个函数有用：

    toArray() {
        return [
            ...(this.left ? this.left.toArray() : []), 
            this.data, 
            ...(this.right ? this.right.toArray() : [])
        ];
    }

这将允许

console.log(treeA.toArray()); //=> [3, 5, 7, 14]

你可以通过join使用空格来获取你的字符串。这个功能让我觉得比你拥有的 printIN 更有用。

我们还可以添加一个静态函数：

    static fromArray(xs) {
        return xs .reduce (function (tree, x) {
            tree.insert(x)
            return tree
        }, new BST())
    }

这将允许我们写

tree = BST .fromArray ([8, 6, 7, 5, 3, 0, 9]);
tree .printIN() //=> [0, 3, 5, 6, 7, 8, 9]

---

我提到我什至不会用 OOP 来做这件事。但是这些天我并没有做太多那样的事情，更喜欢功能性方法。所以，如果你很好奇，这里有另一个完全解决这个问题的方法，只使用函数和在你执行 时没有修改的树insert，而是返回新的树：

const bst = (xs) => 
  xs .reduce ((tree, x) => bstInsert (x, tree), {})

const bstInsert = (x, {left, data, right} = {}) => 
  data == undefined
    ? {data: x}
    : x < data
      ? {data, left: bstInsert (x, left), ...(right ? {right} : {})}
      : {data, ...(left ? {left} : {}), right: bstInsert (x, right)}

const inorder = ({left, data, right} = {}) => [
  ...(left ? inorder(left) : []), 
  data, 
  ...(right ? inorder(right) : [])
]

inorder (bst ([8, 6, 7, 5, 3, 0, 9])) //=> [0, 3, 5, 6, 7, 8, 9]

我不特别推荐这种技术，但 FP 可以成为 OOP 的强大替代方案。