如何檢查嵌套對象是不使用jQuery的另一個對象的後代

我有以下對象。我想要做的是提出一個函數，該函數將指定給定對象是否是id的父代的後代。例如，我想這樣做：lodash歡迎。如何檢查嵌套對象是不使用jQuery的另一個對象的後代

isThisDescendant(7,1) //true 
isThisDescendant(1,7) //false 
isThisDescendant(7,3) //false 
isThisDescendant(3,2) //true 

object = { 
    children : [ 
     { 
      name: 'a', 
      id: 1, 
      children: [ 
       { 
        name: 'b', 
        id: 2, 
        children: [ 
         { 
          name: 'c', 
          id: 3, 
          children: [] 
         }, 
         { 
          name: 'cc', 
          id: 4, 
          children: [] 
         }      
        ] 
       }, 
       { 
        name: 'ba', 
        id: 6, 
        children: [ 
         { 
          name: 'c', 
          id: 8, 
          children: [] 
         }, 
         { 
          name: 'cd', 
          id: 7, 
          children: [] 
         }      
        ] 
       }    
      ] 
     }, 
     { 
      name: 'bb', 
      id: 10, 
      children: [] 
     } 
    ] 
}

來源

2017-10-17 KingKongFrog

'id'應該是一個獨特的價值，但是從我看到它不是（代碼味道！）。有'id'' 3'的兩個實例。你如何處理這種情況？ –

@KingKongFrog你試過了什麼？您應該提供您嘗試過的和沒有工作的代碼，而不是要求解決方案。 – SimplyComplexable

您可以創建遞歸函數將在數組上使用forEach循環，並檢查在任何級別上看到第二個參數後是否存在第一個參數。

var object = {"children":[{"name":"a","id":1,"children":[{"name":"b","id":2,"children":[{"name":"c","id":3,"children":[]},{"name":"cc","id":4,"children":[]}]},{"name":"ba","id":6,"children":[{"name":"c","id":8,"children":[]},{"name":"cd","id":7,"children":[]}]}]},{"name":"bb","id":3,"children":[]}]} 
 

 

 
function isThisDescendant(a, b) { 
 
    var r = false; 
 

 
    function f(a, b, data = object, p = false) { 
 
    if (Array.isArray(data)) { 
 
     data.forEach(function(o) { 
 
     if (p && a == o.id) r = true; 
 
     else f(a, b, o.children, !p ? b == o.id : p) 
 
     }) 
 
    } else f(a, b, data.children, p) 
 
    } 
 
    f(a, b) 
 
    return r 
 
} 
 

 
console.log(isThisDescendant(7, 1)) //true 
 
console.log(isThisDescendant(1, 7)) //false 
 
console.log(isThisDescendant(7, 3)) //false 
 
console.log(isThisDescendant(3, 2)) //true

來源

2017-10-17 23:07:30

考慮到您可能會在比賽結束時提前退出，這不是一種非常昂貴的方法嗎？誠然，樹是非常小的，但由於ID是獨特的，我不明白爲什麼你想要遍歷所有的孩子 – Icepickle

有，但許多解決方案是有效的它需要一定的假設：

這是一次性的東西，或者需要不斷質疑？

如果是一次性操作，那麼您可能會先做一個簡單的廣度優先搜索來尋找父母，然後檢查其子女是否包含您正在尋找的id。這是O（n）。

如果不是，那麼你應該建立一個查找表(id, instance)，然後使用該表來查找你的父母並進行檢查。考慮到兒童的體型小於整個組的大小，這或多或少地是O（1）到O（log n）。
是否對children數組進行排序？

如果對數組進行排序，一旦擁有父實例，您可以對子數組執行二進制搜索以進一步優化它。

來源

2017-10-17 22:29:47

1）一次性事物和2）他們沒有排序。 – KingKongFrog

@KingKongFrog然後很簡單，只需執行任何搜索算法，例如BFS或DFS（取決於您的樹的平均結構）並查找父項，然後檢查是否有任何子項具有您正在查找的「id」。 –

您需要兩個步驟 - 爬行樹找到「容器」，然後從容器爬下來找到後代。

const object = { 
 
    children : [ 
 
     { 
 
      name: 'a', 
 
      id: 1, 
 
      children: [ 
 
       { 
 
        name: 'b', 
 
        id: 2, 
 
        children: [ 
 
         { 
 
          name: 'c', 
 
          id: 3, 
 
          children: [] 
 
         }, 
 
         { 
 
          name: 'cc', 
 
          id: 4, 
 
          children: [] 
 
         }      
 
        ] 
 
       }, 
 
       { 
 
        name: 'ba', 
 
        id: 6, 
 
        children: [ 
 
         { 
 
          name: 'c', 
 
          id: 8, 
 
          children: [] 
 
         }, 
 
         { 
 
          name: 'cd', 
 
          id: 7, 
 
          children: [] 
 
         }      
 
        ] 
 
       }    
 
      ] 
 
     }, 
 
     { 
 
      name: 'bb', 
 
      id: 10, 
 
      children: [] 
 
     } 
 
    ] 
 
} 
 

 
function isThisDescendant(descendentId, containerId, root = object, foundContainer = false) { 
 
    if (root.id === descendentId && foundContainer) return true; //found it inside the container 
 
    if (root.id === descendentId && !foundContainer) return false; //we found the descendent before the container 
 

 
    //recurse down to children 
 
    const newFoundContainer = foundContainer || root.id === containerId; 
 
    const childResults = root.children.map( 
 
     child => isThisDescendant(descendentId, containerId, child, newFoundContainer) 
 
    ); 
 
    return or(childResults); //return true if any of the children hits 
 
} 
 

 
//returns true if any items in the array are true 
 
function or(values) { 
 
    return Boolean(values.filter(Boolean).length); 
 
} 
 

 
    
 
console.log(isThisDescendant(7,1)); //true 
 
console.log(isThisDescendant(1,7)); //false 
 
console.log(isThisDescendant(7,3)); //false 
 
console.log(isThisDescendant(3,2));//true

的幾個注意事項：

性能將在大樹下很差 - 使用索引，以加快（如果每個對象都知道它的父母，你可以走了樹更容易）
我們使用默認參數值，以便對遞歸函數的第一個調用始終始於頂部（root = object）和foundContainer變量爲false所以我們首先尋找容器
因爲這個分支，我已經避免將foundContainer作爲持久狀態來存儲 - 最好是計算出每次傳遞的內容並保持遞歸「純」（不含狀態/副作用）

來源

2017-10-17 22:34:29

這個問題涉及到一個常見問題：在一棵樹「like」結構中找到一個節點。這總是涉及遞歸。

你可以寫一個函數isDescendant(rootObj, valueA, valueB)。這將是這個樣子：

function isDescendant(rootObj, parentId, childId) { 
    const parentNode = findChildren(rootObj, parentId); // Find the parent node 
    if (!parentNode) return false; 
    return !!findChildren(parentNode, childId); // Find the child node 
} 

function findChildren(obj, id) { 
    if (obj.id === id) return obj; 
    if (obj.children) return obj.children.find(c => findChildren(c, id)); 
}

來源

2017-10-17 22:36:16 nicooga

也許有點過於冗長，但也有一些輸入paremeters你可以做這樣的

function findNodeById(branch, id) { 
 
    if (!branch) { 
 
    return null; 
 
    } 
 
    if (branch.id === id) { 
 
    return branch; 
 
    } 
 
    for (let child of branch.children) { 
 
    let result = findNodeById(child, id); 
 
    if (result) { 
 
     return result; 
 
    } 
 
    } 
 
    return null; 
 
} 
 

 
function isThisDescendant(tree, childId, parentId) { 
 
    const parent = findNodeById(tree, parentId); 
 
    if (!parent) { 
 
    return false; 
 
    } 
 
    const child = findNodeById(parent, childId); 
 
    return child !== null; 
 
} 
 

 
const branch = { 
 
    children : [ 
 
     { 
 
      name: 'a', 
 
      id: 1, 
 
      children: [ 
 
       { 
 
        name: 'b', 
 
        id: 2, 
 
        children: [ 
 
         { 
 
          name: 'c', 
 
          id: 3, 
 
          children: [] 
 
         }, 
 
         { 
 
          name: 'cc', 
 
          id: 4, 
 
          children: [] 
 
         }      
 
        ] 
 
       }, 
 
       { 
 
        name: 'ba', 
 
        id: 6, 
 
        children: [ 
 
         { 
 
          name: 'c', 
 
          id: 8, 
 
          children: [] 
 
         }, 
 
         { 
 
          name: 'cd', 
 
          id: 7, 
 
          children: [] 
 
         }      
 
        ] 
 
       }    
 
      ] 
 
     }, 
 
     { 
 
      name: 'bb', 
 
      id: 10, 
 
      children: [] 
 
     } 
 
    ] 
 
}; 
 
console.log(isThisDescendant(branch, 7,1)); //true 
 
console.log(isThisDescendant(branch, 1,7)) //false 
 
console.log(isThisDescendant(branch, 7,3)) //false 
 
console.log(isThisDescendant(branch, 3,2)) //true

來源

2017-10-17 22:36:41 Icepickle

如何檢查嵌套對象是不使用jQuery的另一個對象的後代

回答

相關問題