Comment vérifier si l'objet imbriqué est descendant d'un autre objet n'utilisant jQuery

Question

Je l'objet suivant. Ce que je voudrais faire est de trouver une fonction qui spécifie si l'objet donné est un descendant d'un parent par l'identifiant. Par exemple, je voudrais faire ceci: lodash est le bienvenu.

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: [] 
     } 
    ] 
} 

Answer 1

Vous pouvez créer la fonction récursive utilise la boucle forEach sur les tableaux et vérifie également si le premier paramètre existe après la visualisation du second paramètre à n'importe quel niveau.

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

Answer 2

Il existe de nombreuses solutions, mais pour être efficace, il exige certaines hypothèses:

1. Est-ce une chose unique ou il doit être constamment interrogé? Si c'est une opération ponctuelle, alors vous pouvez probablement partir en faisant une simple recherche en largeur pour rechercher le parent, puis vérifier si ses enfants contiennent les id que vous recherchez. C'est O (n).

   Si ce n'est pas le cas, vous devez alors créer une table de correspondance (id, instance), puis utiliser cette table pour rechercher votre parent et effectuer la vérification. C'est plus ou moins O (1) à O (log n) étant donné que la taille des enfants est bien inférieure à la taille de l'ensemble.

2. -ce que les children tableaux triés?

   Si les tableaux sont triés, une fois que vous avez l'instance parent, vous pouvez effectuer une recherche binaire sur le tableau enfants pour l'optimiser davantage.

Answer 3

Vous aurez besoin de deux étapes ici - en explorant l'arborescence pour trouver le "conteneur", puis en descendant du conteneur pour trouver le descendant.

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

Quelques notes:

• Performance sera très faible sur les grands arbres - indexation utilisation pour accélérer (si chaque objet connaît son parent, vous pouvez marcher jusqu'à la arbre beaucoup plus facilement)
• Nous utilisons des valeurs de paramètres par défaut de sorte que le premier appel à la fonction récursive commence toujours par en haut (root = object) et avec le foundContainer variable comme false donc nous cherchons le conteneur d'abord
• Parce que cela se ramifie, j'ai évité de stocker foundContainer comme état persistant - il est préférable de travailler sur ce qu'il faut passer à chaque fois et garder votre récursivité "pure" (sans état/effets secondaires)

Answer 4

Ce problème implique un problème commun: trouver un nœud dans une structure «semblable» à un arbre. Cela implique toujours la récursivité.

Vous pouvez écrire une fonction isDescendant(rootObj, valueA, valueB).Il ressemblerait à quelque chose comme ceci:

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)); 
} 

Answer 5

Peut-être un peu trop bavard, mais avec une entrée paremeters vous pouvez le faire comme ça

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