DFS выводит все соответствующие элементы и его предка: javascript - PullRequest
Новая
       37

DFS выводит все соответствующие элементы и его предка: javascript

0 голосов
/ 08 февраля 2020

Учитывая 

//  tree data structure
Elephant --> Duck
         --> Hamster -->  Elephant1
                     -->  Elephant2

Hamster --> Elephant --> Fish
        --> Dog -------> Elephant

Dog --> Unicorn
    --> Fish --> Hamster
             --> Elephant --> Elephant

, когда пользовательский термин 'Ele', хотел бы вывести результат так, чтобы все дерево было приведено к следующему формату (который имеет результат сопоставления со своим предком) 

Elephant --> Hamster -->  Elephant1
                     -->  Elephant2  
Hamster --> Elephant 
        --> Dog -------> Elephant
Dog --> Fish  --> Elephant --> Elephant

Учитывая 

this.tree = [
    { id:1, name: 'Elephant',children:[ 
          { id:2, name: 'Duck' },
          { id:3, name: 'Hamster', children: [
                   { id: 4, name: 'Elephant1', id: 5, name: 'Elephant2' }]
          }
    ]},
    { id:5A, name: 'Hamster', children: [
          { id:6, name: 'Elephant', children: [
                  { id:7, name: 'Fish' }
          ]},
          { id:8, name: 'Dog', children: [
                  { id:9, name: 'Elephant' }
          ]}
    ]},
    { id:10, name: 'Dog', children: [
          { id:11, name: 'Unicorn' },
          { id:12, name: 'Fish', children: [
                  { id:13, name: 'Hamster' },
                  { id:14, name: 'Elephant', children: 
                         [{ id:15, name: 'Elephant' }
                  ]},
          ]}
    ]},
    { id:16, name: 'Elephant', children: [
          { id:17, name: 'Duck' }, 
          { id:18, name: 'Hamster', children: [
                 { id:19, name: 'Elephant' }, 
                 { id:20, name: 'Fish' }
          ]}
    ]}
]

Моя попытка:

Я пробовал следующее с использованием обхода в глубину при первом поиске, но возникла проблема с включением его предка при его у детей есть соответствующий термин. В настоящее время код печатает только результат сопоставления дочерних элементов, но не его предка. Я на полпути к решению (вероятно, нуждаюсь в небольшом изменении в моем решении попытки), но у меня возникают проблемы с возвратом. Я искал ресурсы в DFS и был бы признателен, если бы кто-нибудь знал об этом. 

onSearch(term) {
    let found = this.search(term, JSON.parse(JSON.stringify(this.tree)));
    console.log(found);
}

search(term, parent, path, basket) {
    let fork = path.slice(0);

    let found, { name, id, children } = parent;
    let nameId = name + ':' +id;

    fork.push(nameId);
    if (name.toLowerCase().indexOf(term) !== -1) {
        basket.push(fork);
        fork = [];
        return basket
    } 
    if (!!children && children.length > 0) {
        for (let child of parent.children) {
            this.search(term, child, fork, basket)  
        }
        return basket;
    } 

    if (children.length === 0) {
        return [];
    }
  }

this.onSearch('elep');

Однако приведенное выше решение для попытки возвращает приведенный ниже результат, который не совсем верен. 

Elephant  --> Hamster -->  Elephant1 

Hamster --> Elephant  
        --> Dog -------> Elephant

Dog  --> Fish  --> Elephant

Желание Решением является вывод 

Elephant --> Hamster -->  Elephant1
                     -->  Elephant2  
Hamster --> Elephant 
        --> Dog -------> Elephant
Dog --> Fish  --> Elephant --> Elephant

1 Ответ

0 голосов
/ 08 февраля 2020

После нескольких попыток нашел следующее решение, которое выведет желаемое решение 

onSearch(term) {
   let found = this.search(term, JSON.parse(JSON.stringify(this.tree)));
   console.log(found);
}
search(term, parent, path, basket) {
    let found, { name, id, children } = parent;
    let nameId = name + ':' +id;

    let fork = path.slice(0);
    fork.push(nameId);

    if (name.toLowerCase().indexOf(term) !== -1) {
        basket.push([fork]);
    } 
    if (!!children && children.length > 0) {
        for (let child of parent.children) {
            this.search(term, child, fork, basket)
        }
        return basket;
    } 
}
...