树递归：如何获取所选树节点的父根

Question

我有一个 json 对象的树状结构

{
  "saxena": {
    "chewning": {
      "betten": {},
      "ching": {},
      "kelley": {}
    },
    "kobrinsky": {
      "karniely": {},
      "naveh": {},
      "rozenfeld": {},
      "shalom": {}
    },
    "schriever": {
      "brinker": {},
      "mcleland": {},
      "merrick": {}
    },
    "vacant": {
      "akers": {},
      "carlton": {
        "marvin": {}
      },
      "fox": {
        "glover": {
          "clements": {},
          "koya": {}
        },
        "holden": {}
      }
    }
  },
  "bill": {
    "phil": {
      "bob": {},
      "smith": {},
      "hello": {}
    },
    "bye": {
      "ok": {},
      "hmm": {},
      "no": {},
      "alright": {}
    }
  }
}

根名是saxena和bill。我想创建一个函数来确定用户搜索的根名称。

对于最简单的情况，如果他们搜索 saxena，它 returns saxena。如果他们 return 账单，它 return 账单。

对于更复杂的情况，如果用户搜索她下面的任何名字，saxena 将被 returned。

例如，如果我搜索 betten、akers、glovers 或 koya，saxena 将被 returned。

如果我搜索 bob、smith 或 alright，bill 将被 returned。

这是我到目前为止的工作。我尝试使用递归，但出于某种原因，当我找到选定的名称时，我 return 未定义。

var findRootName = function(data, ltmName) {
    for (var key in data) {
        if (key == ltmName) {
            return key;
        } else {
            findNode(data[key], ltmName);
        }
    }
}

var findNode = function(data, ltmName) {
    for (var key in data) {
        if (key == ltmName) {
            return key;
        } else {
            findNode(data[key], ltmName);
        }
    }
}

http://jsfiddle.net/gthnfta7/7/

有人可以帮我弄清楚为什么我的递归函数不起作用吗？

Answer 1

问题是在找到节点的情况下您没有返回任何内容。你可以这样写来简化你的函数：

var findParent = function(data, childName) {
  for (var key in data) {
      if (key === childName || findParent(data[key], childName)) {
        return key;
      }
  }
};

Answer 2

如果您需要对同一数据进行多次调用，另一种技术类似于以下内容：

function makeSearcher(data) {
    var paths = (function makePaths(data, parentPath, store) {
        var path = parentPath || [];
        results = store || {};
        Object.keys(data).forEach(function(key) {
            var newPaths = path.concat(key);
            results[key] = newPaths;
            makePaths(data[key], newPaths, results);
        });
        return results;
    })(data);
    return function(key) {
        var path = paths[key];
        return path && path[0];
    };
}

var search = makeSearcher(data);

search('clements'); //=> 'savena'

请注意，内部 makePaths 函数比此处的用途更广泛，因为它也可以用于 return 像

这样的结果

[ "saxena", "vacant", "fox", "glover", "clements" ]

树递归：如何获取所选树节点的父根

Tree Recursion: How to get the parent root of the selected tree node

javascript

tree

recursion

json

dictionary