Résumé des opérations courantes pour les données de structure de l'arbre frontal

Les traces du temps 2021-09-15 04:50:47
sum des op rations courantes


Cet article présente principalement quelques fonctions d'exploitation communes pour les données de structure d'arbre,Comme la traversée d'un arbre、Arbre à liste、Arbre de liste、Recherche de noeuds d'arbre、Recherche de chemin de noeud d'arbre, etc.

Intégration dans des projets réels,Quelques modifications ont été apportées,Comme l'emballage de l'assemblage du cadre de navette,Essentiellement le traitement des données,Filtrage des données et changement d'état, etc,Afficher sur la page.

Les données simulées sont les suivantes:

const provinceList = [
{
id: "1000",
label: "Province de Hubei",
children: [
{
id: "1001",
pid: "1000",
label: "Wuhan",
children: [
{ id: "100101", pid: "1001", label: "Hongshan District" },
{ id: "100102", pid: "1001", label: "District de Wuchang" },
{ id: "100103", pid: "1001", label: "Hanyang District" },
],
},
{ id: "1020", pid: "1000", label: "Xianning" },
{ id: "1022", pid: "1000", label: "Sens de la piété filiale" },
{ id: "1034", pid: "1000", label: "Xiangyang" },
{ id: "1003", pid: "1000", label: " Yichang " },
],
},
{
id: "1200",
value: "Province du Jiangsu",
label: "Province du Jiangsu",
children: [
{ id: "1201", pid: "1200", label: "Nanjing" },
{ id: "1202", pid: "1200", label: "Suzhou" },
{ id: "1204", pid: "1200", label: "Yangzhou" },
],
},
];
Copier le Code

Traversée de l'arbre

Profondeur d'abord traversée

/** * Profondeur d'abord traversée * @params {Array} tree Données de l'arbre * @params {Array} func Fonction d'opération */
const dfsTransFn = (tree, func) => {
tree.forEach((node) => {
func(node);
// Si le Sous - arbre existe ,Appel récursif
if (node.children?.length) {
dfsTransFn(node.children, func);
}
});
return tree;
};
// Imprimer le noeud 
dfsTransFn(tree, (node) => {
console.log(`${node.id}...${node.value}`);
});
Copier le Code

Traversée du cycle de profondeur

Similaire à Broadband First , Pour maintenir une file d'attente . Mais cette fonction est ajoutée en haut de la file d'attente , Et l'étendue d'abord est ajoutée à la fin de l'équipe .

const dfsTreeFn = (tree, func) => {
let node,
list = [...tree];
// shift()- Prenez le premier 
while ((node = list.shift())) {
func(node);
// Si le Sous - arbre existe ,Appel récursif
// Le noeud enfant est ajouté à l'avant de la file d'attente `unshift`
node.children && list.unshift(...node.children);
}
};
Copier le Code

Largeur d'abord traversée

/** * Largeur d'abord traversée * @params {Array} tree Données de l'arbre * @params {Array} func Fonction d'opération */
const bfsTransFn = (tree, func) => {
let node,
list = [...tree];
// shift()- Prenez le premier ;pop()- Prends le dernier 
while ((node = list.shift())) {
func(node);
// Si le Sous - arbre existe ,Appel récursif
node.children && list.push(...node.children);
}
};
// Imprimer le noeud 
bfsTransFn(tree, (node) => {
console.log(`${node.id}...${node.value}`);
});
Copier le Code

ic_transfer_5.png

Arbre à liste

Profondeur d'abord récursive

const dfsTreeToListFn = (tree, result = []) => {
if (!tree?.length) {
return [];
}
tree.forEach((node) => {
result.push(node);
console.log(`${node.id}...${node.label}`); // Imprimer les informations du noeud 
node.children && dfsTreeToListFn(node.children, result);
});
return result;
};
Copier le Code

Largeur d'abord récursive

const bfsTreeToListFn = (tree, result = []) => {
let node,
list = [...tree];
while ((node = list.shift())) {
result.push(node);
console.log(`${node.id}...${node.label}`); // Imprimer les informations du noeud 
node.children && list.push(...node.children);
}
return result;
};
Copier le Code

ic_transfer_6.png

Réalisation du cycle

export const treeToListFn = (tree) => {
let node,
result = tree.map((node) => ((node.level = 1), node));
for (let i = 0; i < result.length; i++) {
// Pas de noeud enfant, Sauter la boucle actuelle ,Passez au cycle suivant
if (!result[i].children) continue;
// Il y a des noeuds enfants ,Traverser les noeuds enfants, Ajouter des informations de niveau 
let list = result[i].children.map(
(node) => ((node.level = result[i].level + 1), node)
);
// Ajouter des noeuds enfants au tableau 
result.splice(i + 1, 0, ...list);
}
return result;
};
Copier le Code

Arbre de liste

const listToTreeFn = (list) => {
// Crééid=>nodeCartographie de
let obj = list.reduce(
// map-Accumulateur,node-Valeur actuelle
(map, node) => ((map[node.id] = node), (node.children = []), map),
// Valeur initiale
{}
);
return list.filter((node) => {
// Traitement de la recherche de l'élément parent :
// 1. Traverséelist:La complexité temporelle estO(n), Et traverser la boucle , La complexité temporelle globale devient O(n^2)
// 2. Valeur de l'objet :La complexité temporelle estO(1), La complexité temporelle globale est O(n)
obj[node.pid] && obj[node.pid].children.push(node);
// Le noeud racine n'a pas pid, Comme condition de filtration 
return !node.pid;
});
};
Copier le Code

Trouver des noeuds

Déterminer si un noeud existe ,L'existence renvoie true,Sinon, retournez à false

const treeFindFn = (tree, func) => {
for (let node of tree) {
if (func(node)) return node;
if (node.children) {
let result = treeFindFn(node.children, func);
if (result) return result;
}
}
return false;
};
// Code d'essai
let findFlag1 = treeFindFn(provinceList, (node) => node.id === "1020");
let findFlag2 = treeFindFn(provinceList, (node) => node.id === "100125");
console.log(`1020 is ${JSON.stringify(findFlag1)}, 100125 is ${findFlag2}`);
// Imprimer les résultats:
1020 is {"id":"1020","pid":"1000","label":"Xianning","key":"1020","title":"Xianning","level":2,"children":[]}, 100125 is null
Copier le Code

Trouver le chemin du noeud

const treeFindPathFn = (tree, func, path = []) => {
if (!tree) return [];
for (let node of tree) {
path.push(node.id);
if (func(node)) return path;
if (node.children) {
const findChild = treeFindPathFn(node.children, func, path);
if (findChild.length) return findChild;
}
path.pop();
}
return [];
};
// Code d'essai
let findPathFlag = treeFindPathFn(
provinceList,
(node) => node.id === "100102"
);
console.log(`100102 path is ${findPathFlag}`);
// Imprimer les résultats
100102 path is 1000,1001,100102
Copier le Code

ic_transfer_7.png

Application de la fonction réelle

Présentation de la page

<template>
<div class="demo-block">
<div class="demo-block-title"> Fonction de traitement des données de la boîte de navette :</div>
<div class="demo-block-content">
<div class="demo-block-title">Données brutes:</div>
<a-tree blockNode checkable defaultExpandAll :tree-data="provinceData" />
</div>
<div class="demo-block-content" style="margin-left: 40px;vertical-align: top;" >
<div class="demo-block-title"> Données post - traitement :filterSourceTreeFn</div>
<a-tree blockNode checkable defaultExpandAll :tree-data="optProvinceData" />
</div>
</div>
</template>
<script> import * as R from "ramda"; import provinceList from "./mock.json"; export default { data() { return { provinceData: [], optProvinceData: [], }; }, }; </script>
<style lang="scss"></style>
Copier le Code

Conversion des données (Traversée)

Convertir les données analogiques en données requises par le composant ,Traverser les données,Ajouter title Et key Champ

const treeTransFn = (tree) =>
dfsTransFn(tree, (o) => {
o["key"] = o.id;
o["title"] = o.label;
});
this.provinceData = treeTransFn(provinceList);
Copier le Code

ic_tree_4.png

Désactiver le noeud sélectionné

const disabledTreeFn = (tree, targetKeys) => {
tree.forEach((o) => {
let flag = targetKeys.includes(o.id);
o["key"] = o.id;
o["title"] = flag ? `${o.label}(Configuré)` : o.label;
o["disabled"] = flag;
o.children && disabledTreeFn(o.children, targetKeys);
});
return tree;
};
this.provinceData = disabledTreeFn(provinceList, ["100101", "1022", "1200"]);
Copier le Code

ic_tree_5.png

Filtre de noeud sélectionné

Traitement des données du cadre de données source , Filtrer les noeuds sélectionnés ,Non.

/** * Filtre de noeud sélectionné * @params {Array} tree Données de l'arbre * @params {Array} targetKeys Données sélectionnéeskeyEnsemble * Les conditions de filtration sont : Le noeud actuel et ses descendants n'ont pas de données qualifiées */
const filterSourceTreeFn = (tree = [], targetKeys = [], result = []) => {
R.forEach((o) => {
// 1. Déterminer si le noeud actuel contient des données qualifiées :- Oui.-Continue.;Non-Filtration
if (targetKeys.indexOf(o.id) < 0) {
// 2. Déterminer s'il y a des noeuds enfants :- Oui.-Continue.;Non-Retour direct
if (o.children?.length) {
// 3. Traitement récursif des noeuds enfants 
o.children = filterSourceTreeFn(o.children, targetKeys);
// 4. Noeud enfant présent , Et les noeuds enfants ont également des noeuds enfants qualifiés ,Retour direct
if (o.children.length) result.push(o);
} else {
result.push(o);
}
}
}, tree);
return result;
};
this.optProvinceData = treeTransFn(
filterSourceTreeFn(R.clone(provinceList), ["100101", "1022", "1200"])
);
Copier le Code

ic_tree_6.png

Parfois..., Lorsque le noeud parent satisfait aux conditions , Mais s'il n'y a pas de noeud enfant satisfaisant , Retour normal des données . La méthode ci - dessus n'est pas admissible , Est remplacé par ce qui suit: .

export const filterSourceTreeFn = (tree = [], targetKeys = []) => {
return R.map(
(o) => {
// 2. Noeud enfant présent ,Traitement récursif
if (o.children?.length) {
o.children = filterSourceTreeFn(o.children, targetKeys) || [];
}
return o;
},
// 1. Filtrer les données non admissibles 
R.filter(
(r) => targetKeys.indexOf(r.id) < 0,
// Évitez de modifier directement les données originales ,BesoinR.clone()On s'en occupe.
R.clone(tree)
)
);
};
Copier le Code

ic_tree_9.png

Le noeud sélectionné reste

Traitement des données cibles , Afficher uniquement les noeuds sélectionnés , Autres données filtrées

// Les conditions de filtration sont : Le noeud courant ou son descendant a des données qualifiées 
filterTargetTreeFn = (tree = [], targetKeys = []) => {
return R.filter((o) => {
// Le noeud actuel est qualifié ,Retour direct
if (R.indexOf(o.id, targetKeys) > -1) return true;
// Sinon, voir si ses noeuds enfants sont qualifiés 
if (o.children?.length) {
// Appel récursif du noeud Enfant 
o.children = filterTargetTreeFn(o.children, targetKeys);
}
// L'existence d'un noeud descendant renvoie 
return o.children && o.children.length;
}, tree);
};
this.optProvinceData = treeTransFn(
filterTargetTreeFn(R.clone(provinceList), ["100101", "1022", "1200"])
);
Copier le Code

ic_tree_7.png

Filtrage des mots clés

export const filterKeywordTreeFn = (tree = [], keyword = "") => {
if (!(tree && tree.length)) {
return [];
}
if (!keyword) {
return tree;
}
return R.filter((o) => {
// 1. Le noeud parent satisfait aux conditions ,Retour direct
if (o.title.includes(keyword)) {
return true;
}
if (o.children?.length) {
// 2. Sinon, Quand il y a des noeuds enfants ,Traitement récursif
o.children = filterKeywordTreeFn(o.children, keyword);
}
// 3. Lorsque le noeud enfant satisfait aux conditions ,Retour
return o.children && o.children.length;
// Évitez de modifier les données originales ,À utiliser iciR.clone()On s'en occupe.
}, R.clone(tree));
};
Copier le Code

ic_tree_8.png

版权声明
本文为[Les traces du temps]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/09/20210914174203473F.html

  1. Front and back end data interaction (V) -- what is Axios?
  2. Windows configures nginx to boot automatically
  3. Des questions d'entrevue communes à Tomcat pour discuter de votre compréhension de la technologie de verrouillage distribué,
  4. JS handscrap, Classic interview question, web front end Development Process
  5. Android 400 questions d'entrevue pour vous aider à entrer dans l'usine, un tour pour vous apprendre à comprendre netty
  6. Développement et projet d'application Web statique côté PC
  7. Recommandé pour le tutoriel Spring Framework, 2021 dernière question d'entrevue d'embauche de la société aiqiyi Java,
  8. La dernière revue scientifique de l'académicien Luo Liqun: architecture de la boucle neuronale pour stimuler la nouvelle Ia
  9. [partage d'expérience de travail], 2021 les dernières questions d'entrevue Java de Baidu, Headlines, etc.
  10. Lisez l'analyse de 497 questions pour l'entrevue d'ingénieur principal Android et vérifiez les lacunes.
  11. Grâce à cette collection de questions d'entrevue d'automne, le salaire de saut d'emploi et l'entrevue de développement audio et vidéo ont doublé.
  12. Prenez d'un coup l'offre de Tencent meituan et jetez un coup d'oeil à cette copie de l'entrevue de printemps!
  13. L'expérience et l'expérience d'un Maverick Java en matière d'entrevue sur les MTD, l'expérience de l'entrevue d'embauche du printemps Java en 2021,
  14. Vue中自定义列表复选框和全选框-案例
  15. Vue bidirectional binding (V-model bidirectional binding,. Sync bidirectional binding,. Sync transfer object)
  16. CSS text overflow ellipsis summary, as you wish
  17. C'est la mode la plus étrange que j'ai jamais vue.
  18. Cases à cocher et toutes les cases à cocher de la liste personnalisée en vue - CAS
  19. Vue bidirectional binding (V-model bidirectional binding,. Sync bidirectional binding,. Sync transfer object)
  20. Vue3.0 using Gaode map to obtain longitude and latitude information
  21. Front end interview daily 3 + 1 - day 877
  22. Vue bidirectional binding (V-model bidirectional binding,. Sync bidirectional binding,. Sync transfer object)
  23. React realizes the function of copying pictures with one click
  24. White space, word break and word wrap are the three most basic and confusing attributes in CSS - thoroughly understand
  25. Trois ans d'expérience d'entrevue avec une femme de programmation diplômée, une réflexion sur la cohérence de l'expiration des données de redis Master slave Node,
  26. Résumé de l'entrevue Android de Dachang, carte technique Android
  27. Un plan de carrière Java correct, découvrez les questions que vous devez poser lors de l'entrevue d'embauche du printemps Java de cette année.
  28. Le résumé de l'entrevue Android de Dachang est en retard
  29. Un article vous a appris à gérer les entrevues sur le Web, à partager 350 vraies questions d'entrevue Java,
  30. Jquery Tools Methodology collation, Sharing a little interview Experience
  31. Jquery plug - in urianchor, app front end Development
  32. $in jquery, Visualized Web Development Tool
  33. Le développement Java doit être fait. Les entrevues https demandent souvent une analyse complète.
  34. vue v-if未生效问题
  35. vue动态改变组件外部元素样式
  36. Jdk's Past Life: The Classic Features of Thin Number - java5 - - - 15 -, webfront Development
  37. Résumé des questions d'entrevue pour les ingénieurs en développement Java, analyse des questions d'entrevue à haute fréquence Dubbo,
  38. The new front-end lady asked: there was a 404 problem refreshing the page in Vue routing history mode
  39. A Simple Css Meun
  40. Vue modifier dynamiquement le style de l'élément externe du composant
  41. Vue V - si problème non valable
  42. N'osez pas vous opposer à l'intervieweur et obtenir des commentaires personnels des stagiaires d'offer Ali après cinq rondes d'entrevue.
  43. Améliorer continuellement leur capacité à créer des primes, et les questions d'entrevue Java d'Alibaba Huawei Tencent et d'autres grandes usines sont sautées en octets.
  44. The new front-end lady asked: there was a 404 problem refreshing the page in Vue routing history mode
  45. Who doesn't want to make a scratch music by himself? Scratch music is realized by native JS
  46. Learn XPath to help climb the data of major e-commerce platforms in the Mid Autumn Festival
  47. vue動態改變組件外部元素樣式
  48. vue v-if未生效問題
  49. Je ne comprends pas comment la machine virtuelle JVM peut encore interviewer, et j'ai terminé ce dictionnaire d'entrevue Java de 1307 pages.
  50. Dongxh, mid autumn festival gifts 🥮, [CSS starry sky realization, Mid Autumn Festival poem]
  51. What if you want to see the moon and don't want to go out
  52. Mid Autumn Festival, Chang'e looks at the moon
  53. [Pixi] super beautiful! How to make mid autumn festival scene level animation!!
  54. Echarts realizes the rotation of the moon (super simple, you can see it at a glance)
  55. Dart mixin full resolution
  56. Some suggestions on Vue code readability | comments are rewarded
  57. 120 lines of code to achieve pure web video editing
  58. Yang yangsun took a selfie to celebrate his 30th birthday, and Wang Yanlin sent blessings.
  59. Comment passer une entrevue avec une entreprise Internet de première ligne, Android Classic Getting started tutoriel
  60. Comment essayer un développeur Android vraiment niveau, 【 résumé de l'entrevue 】