TreeNode搜索Javascript

Question

我有一个叫TreeNode的类

class TreeNode {
  constructor(name) {
    // Name of the node visible to user. It is string
    self.name = name;

    //  Children of the node. it is array of TreeNode
    self.children = [];

    // If this field is true, children of the Node are shown to the user
    self.expanded = false;

    // If this field is true, it means that the node matches the current search and it is emphasized
    self.matched = false;
  }

任务是执行以下操作: /*此函数返回原始树的一个新子树，它满足以下要求：

• 函数不修改原始树。
• “Node与搜索词匹配”表示Node的名称包含“search”作为子字符串(不区分大小写)。
• 节点包含在结果子树中，如果节点、其祖先之一或其后代之一匹配搜索。
• 如果Node与搜索匹配，则其匹配属性必须设置为true，否则为false。
• 如果节点的至少一个子代与搜索匹配，则Node的展开属性必须设置为true，否则为false @返回TreeNode收空*/ makeTreeForSearchQuery(搜索){ //在这里执行返回null；}

我在课堂上有一个函数

makeTreeForSearchQuery(search)
{
if (self.children != null)
    {
        for(var i=0; i < self.children.length; i++)
        {
            self.children[i]= makeTreeForSearchQuery(search);
            if(children.matched[i] == true)
            {
                //self.parent = children.matched[i];
                //self.expanded = true;
            }
            
            //Something needs to be done here
        }
    }
        if(self.name === search)
        {
            self.matched = true;
            console.log(self.name);
        }
    
    return TreeNode;
}

我需要得到这样的结果:搜索=‘2’

结果树：

根匹配:false，展开:true

左匹配:false，展开:true

两个匹配:true，展开:false

Example
 * Original tree
 *       root
 *      |    \
 *    left  right
 *   |   |  \    \
 * one two three four
 *
 * Search = 'two'

 Result tree:
 *     root - matched:false, expanded:true
 *      |
 *    left - matched:false, expanded:true
 *      |
 *     two - matched:true, expanded:false

 Or if we describe it in JSON format
 Original tree
  {
  name: "root",
  expanded: false,
  matched: false,
  children: [
    {
      name: "left",
      expanded: false,
      matched: false,
      children: [
        {
          name: "one",
          expanded: false,
          matched: false,
          children: [],
        },
        {
          name: "two",
          expanded: false,
          matched: false,
          children: [],
        },
      ],
    },
    {
      name: "right",
      expanded: false,
      matched: false,
      children: [
        {
          name: "three",
          expanded: false,
          matched: false,
          children: [],
        },
        {
          name: "four",
          expanded: false,
          matched: false,
          children: [],
        },
      ],
    },
  ],
};
Result Tree:
{
  name: "root",
  expanded: true,
  matched: false,
  children: [
    {
      name: "left",
      expanded: true,
      matched: false,
      children: [
        {
          name: "two",
          expanded: false,
          matched: true,
          children: [],
        },
      ],
    },
  ],
}

Answer 1

对于我来说，对同样的问题添加第二个答案是非常罕见的，但是前一次，它有许多有趣的讨论和无数的编辑，似乎太满了。下面是另一种方法，它似乎捕获了前面那次传递中缺少的一个需求：

​

const treeNode = (name, children = []) => 
  ({name, expanded: false, matched: false, children})

const match = (query) => ({name, children: kids}, forced = false) => {
  const matched = name .toLowerCase () .includes (query .toLowerCase())
  const allChildren = kids .map (child => match (query) (child, forced || matched)) 
  const children = forced || matched ? allChildren : allChildren .filter (n => n .matched || n .expanded)
  const expanded = children .length > 0

  return {name, expanded, matched, children}
}

const tree = treeNode ("root", [treeNode ('left', [treeNode ('one'), treeNode ('two')]), treeNode ('right', [treeNode ('three'), treeNode ('four')])])

console .log ('Original tree', tree)
console .log ('Query "Two" result', match ('Two') (tree))  // two
console .log ('Query "o" result', match ('o') (tree))      // root, one, two, four
console .log ('Query "g" result', match ('g') (tree))      // right
console .log ('Original tree is not modified', tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

​

我们继续按照该答案的更新2进行，采用简单的功能方法和命令式函数体。

这里的实质区别在于，我们为match (query)返回的函数默认了一个附加参数:参数force，默认为false。这是用来决定我们是保留所有的孩子，还是只保留那些自己匹配或有匹配后代的孩子。在对子节点进行递归调用之前，我们检查当前节点是否匹配，如果匹配，则将这些调用的新forced标志设置为true。这是为了处理我在第一个答案中遗漏的要求：

节点包含在结果子树中，如果节点、(它的祖先之一或其后代之一)与搜索匹配。

如果一个节点匹配，那么它的所有后代都应该包括在内。这能解决这个问题。这并不能解决OP对先前的回答的评论，即代码在搜索Two时出错了。据我所知，这会创建与示例相同的输出，而逻辑的这一部分在这里不应该改变。

AFAICT，模块化从构造函数到工厂函数的更改，这现在符合所有的需求，除了这个：

返回TreeNode \\ null

当提供treeNode对象时，这将始终返回一个对象。我不知道这里的null案例是什么意思。但我们没有。

由于我们深入研究了前面的答案的参数处理，也许我们应该在这里看看它。这使用了一种可以通过调用代码覆盖我们的默认参数的导致问题技术。如果我们对此感到关切，因为有人可能会调用someArray .map (match ('Two'))，或者因为我们根本不知道如何使用该函数，我们可以编写一个使用该额外参数的私有实现，并从一个公共包装器函数中提供它，如下所示：

const _match = (query) => ({name, children: kids}, forced) => {
  const matched = name .toLowerCase () .includes (query .toLowerCase())
  const allChildren = kids .map (child => _match (query) (child, forced || matched)) 
  const children = forced ? allChildren : allChildren .filter (n => n .matched || n.expanded)
  const expanded = children .length > 0
  return {name, expanded, matched, children}
}

const match  = (query) => (node) => 
  _match (query) (node, false)

同样，这应该是直接转换为面向对象的风格。

更新

同样，向OO转换似乎相对简单。这个版本应该做到：

​

class TreeNode {
  constructor (name, children = []) {
    this .name = name
    this .expanded = false
    this .matched = false
    this .children = children
  }
  
  match (query, forced = false) {
    const matched = this .name .toLowerCase () .includes (query .toLowerCase())
    const allChildren = this .children .map (child => child .match (query, forced || matched)) 
    const children = forced || matched ? allChildren : allChildren .filter (n => n .matched || n .expanded)
    const newNode = new TreeNode (this .name, children)
    newNode .expanded = children .length > 0
    newNode .matched = matched
    
    return newNode
  }
}

const tree = new TreeNode ("root", [new TreeNode ('left', [new TreeNode ('one'), new TreeNode ('two')]), new TreeNode ('right', [new TreeNode ('three'), new TreeNode ('four')])])

console .log ('Original tree', tree)
console .log ('Query "Two" result', tree .match ('Two'))  // two
console .log ('Query "o" result', tree .match ('o'))      // root, one, two, four
console .log ('Query "g" result', tree .match ('g'))      // right
console .log ('Original tree is not modified', tree)

.as-console-wrapper {max-height: 100% !important; top: 0}

​

我们所要做的就是获取match的主体，使其成为一个方法，并将treeNode参数(node和children)的所有用法转换为对this属性的引用，并对对match的递归引用执行同样的操作。

在进行此转换时，我在尝试另一个测试用例('g')时注意到了一个错误。它在原始版本和这个版本中都是固定的：

-   const children = forced ? allChildren : allChildren .filter (n => n .matched || n .expanded)
+   const children = forced || matched ? allChildren : allChildren .filter (n => n .matched || n .expanded)