树形结构

树形构造先序遍历树实际公司我的项目中常常应用到树形构造性能,如机械部件的保护等,当数据量达到肯定级别会有性能问题: 查问效率低,无论是在数据库中做递归还是在代码中递归都会节约计算性能如果一次性查给前台,数据量大的状况话下浏览器会卡顿当查问退出其余业务逻辑的时候会导致代码复杂度减少Modified Preorder Tree Traversal (改良先序遍历树）网上查找计划的时候看到这种解决方案, 该计划能够疾速查找子孙节点。 原理设节点有left,right, parentId三个字段,根节点left=1, right=2;节点插入子节点的时候, 令新节点的left=parent.right,right=left+1;找出所有节点满足left,right大于新增点的left,right, 另这些节点的left和right值加2;如此咱们能失去相似上面的构造 跟二叉树的先序遍历很像 如此，当咱们须要查问江苏上面所有的子孙节点的时候, 能够用以下sql去查问SELECT * FROM table_name where lft > 2 and rgt < 11; 插入删除节点这种构造对于增删操作效率较低, 须要更改大量节点的左右值, 能够写成存储过程 插入: 节点插入子节点的时候, 令新节点的left=parent.right,right=left+1;删除: 每删一个节点, 相当于缩小了right-left+1个子节点, 对于parent.right>left和parent.left >left的状况, 减去delta即可实现表构造CREATE TABLE `nested_category` ( `category_id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(255) CHARACTER SET utf8mb4 NOT NULL, `parent_id` int(255) NOT NULL DEFAULT '0', `lft` int(255) NOT NULL, `rgt` int(255) NOT NULL, `deleted` tinyint(255) NOT NULL DEFAULT '0', PRIMARY KEY (`category_id`)) ENGINE=InnoDB AUTO_INCREMENT=19 DEFAULT CHARSET=latin1插入存储过程CREATE DEFINER=`root`@`%` PROCEDURE `insert_node_into_nested_category`(IN `nodeId` int,IN `namee` varchar(255))BEGIN #Routine body goes here... DECLARE lftt int(255); DECLARE rgtt int(255); DECLARE parentId int; SELECT category_id, rgt, rgt+1 INTO parentId, lftt, rgtt FROM nested_category WHERE category_id = nodeId; # SELECT parentId,lftt,rgtt,nodeId,namee; UPDATE nested_category SET lft=lft+2 WHERE lft > lftt; UPDATE nested_category SET rgt=rgt+2 WHERE rgt >= lftt; INSERT into nested_category (name,lft,rgt,parent_id) VALUES (namee,lftt,rgtt,parentId);END删除存储过程CREATE DEFINER=`root`@`%` PROCEDURE `del_node_from_nested_category`(IN `nodeId` int)BEGIN #Routine body goes here... DECLARE lftt,rgtt,delta int; SELECT lft, rgt, rgt-lft+1 INTO lftt, rgtt, delta FROM nested_category WHERE category_id=nodeId; # select lftt,rgtt,delta; UPDATE nested_category SET lft=lft-delta where lft > rgtt; UPDATE nested_category set rgt=rgt-delta WHERE rgt > rgtt; DELETE from nested_category WHERE category_id=nodeId or parent_id=nodeId;END测试 ...

奢侈并查集 // 每个点的父亲节点int p[N];// 每个汇合的大小int sz[N];void init(int n) { for (int i = 1; i <= n; i ++ ) { p[i] = i; sz[i] = 1; }}int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];}void merge(int x, int y) { x = find(x), y = find(y); p[x] = y; sz[y] += sz[x];}带门路压缩的并查集 // 每个点的父亲节点int p[N];// 每个点间隔根节点的间隔int dist[N];// 每个汇合的大小int sz[N];void init(int n) { for (int i = 1; i <= n; i ++ ) { p[i] = i; dist[i] = 0; sz[i] = 1; }}int find(int x) { if (p[x] == x) return x; int root = find(p[x]); d[x] += d[p[x]]; return p[x] = root;}void merge(int x, int y) { x = find(x), y = find(y); p[x] = y; d[x] = sz[y]; sz[y] += sz[x];}

过滤/筛选树节点又是树，是我跟树杠上了吗？—— 不，是树的问题太多了！ 相干文章举荐： 应用递归遍历并转换树形数据（以 TypeScript 为例）从列表生成树 (JavaScript/TypeScript) 过滤和筛选是一个意思，都是 filter。 对于列表来说，过滤就是丢掉不须要的，留下须要的。但对于树来说就得分状况了。 如果想“过滤掉”（丢掉）某些节点，会把它的子节点一并摈弃，就像砍树枝一样，干之不存，枝将焉附？这种状况多是去除不须要的子树。如果是想“查找”某些节点，会将找到的节点及其上溯到根的所有节点都保留下来。对于找到的节点，除了保留其残缺门路之外，对其子树还有两种解决形式： 一种是“到此为止”，也就是说，如果其子树中没有符合条件的节点，那就不须要了，砍掉。须要定位到符合条件的节点以便后继操作是采纳这种形式，这也是最罕用的查找形式。另一种是保留其残缺子树。如果须要应用符合条件节点的子节点（比方抉择指定部门及其子部门）会采纳这种形式。过滤和查找的次要区别在于：“过滤”通常会遇到不合乎保留条件（或合乎剔除条件）的节点就间接砍掉，不论其子树中是否还存在合乎保留条件的节点；而查找则会始终找到叶节点上，只有整条门路都没有合乎保留条件的节点，才会从其某个先人节点上砍掉（先人节点是否保留取决于其下是否存在合乎保留条件的子孙节点）。 上面一样一样来。示例代码应用 TypeScript 编写，示例数据起源于从列表生成树 (JavaScript/TypeScript) 一文，同时应用该文中定义的节点类型接口： interface TreeNode { id: number; parentId: number; label: string; children?: TreeNode[]}过滤掉不须要的节点过滤掉不须要的节点，思路比较简单： 遍历以后节点的所有子节点，须要的留，不须要的删对留下的节点，通过递归进行过滤按此思路，TypeScript 代码是 /** * @param nodes 要过滤的树节点集（多根） * @param predicate 过滤条件，返回 `true` 保留 * @returns 过滤后的树节点集 */function filterTree( nodes: TreeNode[] | undefined, predicate: (node: TreeNode) => boolean): TreeNode[] | undefined { if (!nodes?.length) { return nodes; } // 间接应用 Array 的 filter 能够过滤当层节点 return nodes.filter(it => { // 不符合条件的间接砍掉 if (!predicate(it)) { return false; } // 符合条件的保留，并且须要递归解决其子节点 it.children = filterTree(it.children, predicate); return true; });}如果对示例数据（见前文）进行过滤，仅保留 id 是偶数的节点，那后果是 ...

什么是差分？定义：差分就是数组中每一项都与前一项做差，最初得出的序列。例如：数组：2,5,3,7,2,3差分后的序列：2,3,-2,4,-5,1,-3留神：第一个数与原数组雷同，相当于2-0；最初一个数与原数组互为相反数，相当于0-3；差分的性质：1.差分序列的前缀和就是原数组；2.将原数组在[L,R]区间上的数全副加1，相当于让差分数组在L处+1，在R+1处-1； 树上差分思考差分的一个利用：图片起源：https://blog.csdn.net/a135193... 树上差分的两种思路：1.找被所有门路独特笼罩的边。例题：洛谷：https://www.luogu.com.cn/prob...剖析见代码： //1.找被所有门路独特笼罩的边。#include <algorithm>#include <iostream>#include <stdio.h>#include <cstring>#include <vector>using namespace std;const int N = 300010;int fa[N][26];int depth[N], dist[N];int tmp[N], pre[N];int cnt,flag;//tmp存节点呈现的次数，即节点与节点父亲的边在所有门路中呈现的次数//pre存节点与节点父亲之间的边，本题中存的是边权，别的题中也有可能存编号int n, m;struct node{ int s, t; int lca;} path[N];int head[N], nex[2 * N], val[2 * N], to[2 * N], idx;int u, v, w;void add(int u, int v, int w){ to[idx] = v; val[idx] = w; nex[idx] = head[u]; head[u] = idx++;}int que[N];void bfs(int root){ memset(depth, 0x3f, sizeof(depth)); depth[0]=0; depth[root] = 1; int h = 0, t = 0; que[t++] = root; while (h != t) { int top = que[h++]; for (int i = head[top]; ~i; i = nex[i]) { int j = to[i]; int w = val[i]; if (depth[j] > depth[top] + 1) { depth[j] = depth[top] + 1; dist[j] = dist[top] + val[i]; que[t++] = j; pre[j] = val[i]; fa[j][0] = top; for (int k = 1; k <=21; k ++) { fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } }}int get_lca(int u, int v){ if (depth[u] < depth[v]) { swap(u, v); } //第一步：先让u跳到与v同一高度 for (int i = 21; i >= 0; i--) { if (depth[fa[u][i]] >= depth[v]) { u = fa[u][i]; } } if (u == v) //非凡状况，u和v调到同一高度之后重合，只需返回u或v即可 { return u; } //第二步，让u和v跳到最近公共先人的下一层 for (int i = 21; i >= 0; i--) { if (fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } } return fa[u][0]; //再向上跳一步就是root}int judge(int a,int f,int cnt,int maxn){ for(int i=head[a];~i;i=nex[i]) { int j=to[i]; if(j==f) { continue; } tmp[a]+=judge(j,a,cnt,maxn); } if(tmp[a]==cnt&&pre[a]>=maxn) { flag=1; } return tmp[a];}bool check(int x){ memset(tmp, 0, sizeof(tmp)); cnt = 0,flag=0; int maxn = 0; for (int i = 1; i <= m; i++) { int dis = dist[path[i].s] + dist[path[i].t] - 2 * dist[path[i].lca]; if (dis > x) { cnt++; maxn = max(maxn, dis - x); //s,t加一，最近公共先人-2 tmp[path[i].s]++; tmp[path[i].t]++; tmp[path[i].lca] -= 2; } } if (!cnt) { return true; } judge(1,0,cnt,maxn); if(flag) { return true; } return false;}int main(){ scanf("%d %d", &n, &m); memset(head, -1, sizeof(head)); for (int i = 0; i < n - 1; i++) { scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, w); } bfs(1); for (int i = 1; i <= m; i++) { scanf("%d %d", &path[i].s, &path[i].t); path[i].lca = get_lca(path[i].s, path[i].t); } //二分找正确答案 long long int l = 0, r = 3000000000; while (l < r) { int mid = (l + r) / 2; if (check(mid)) { r = mid; } else { l = mid + 1; } } cout << l << endl; return 0;}

少数状况下，从服务端拿到用于树形显示的数据，自身是立体的，也就是列表。这是因为关系型数据库是以“行”为单位保留数据，所以它保留了每一个节点的数据，而这个数据中蕴含了它与父节点之间的分割（比方 parentId）。 前端要以树形显示这样的列表数据，须要把列表数据转换成树形构造数据。这个的树形构造是指：每个节点数据中都含有其子节点集（通常是 children 属性）。所以树形结节的数据结构次要须要蕴含如下信息（TypeScript 数据结构申明）： interface TreeNodeBase<TKey extends string | number = number> { id: TKey; parentId: TKey children?: TreeNodeBase<TKey>[]}这里应用了 TypeScript 的泛型语法来形容树节点构造。从天然语义不难明确： 树节点的 id（包含 parentId）是 string 或者 number 类型，较为少见的状况下也可能是混合类型。树节点蕴含一个 parentId，因为这个 parentId 不是可选的（没用 ? 号申明），所以根节点通常会用一个非凡值，或者不应该存在的 ID 值，比方 0（如果是数据库自增字段，个别会从 1 开始）树节点蕴含一个可选的子节点集 children，其每个元素了以后元素是雷同的类型定义 TKey 这个类型参数的作用就是为了束缚子节点类型必须和父节点统一，防止父节点的 id 是 string 类型，子节点的 id 却搞成了 string 这种状况（混合类型 id 的状况不含在内）科普完树节点的数据结构，再来说转换过程。一般来说可能会在三个阶段进行转换： 后端送进去之前先解决好前端拿到之后本人转换，再用转换后数组去渲染页面前端应用的 UI 组件自带转换性能，不须要开发者去操心（比方 zTree）这里就以 JS/TS 为例来说说如何进行转换。语言不重要，重要的是该如何来思考，以及应用什么办法进行转换。这里同时应用 JS 和 TS 的起因在于：带相似的 TS 能够清晰地形容数据结构，而 JS 代码可能少数人看起来更没有压力。 一、筹备示例数据（随机产生）以列表示意的树形数据，其每一条（行）肯定须要分明的形容这个节点的三个因素： 本身标识（ID），通常用 id、key、name 等属性名，它能惟一标识一个节点与父节点的关系，通过应用 parentId、upstreamId 等名称，分明的指明其父节点节点本人携带的数据，比方显示的文本，title、label 等，和一些其余数据。为了疾速筹备示例数据，咱们应用一个最简略，属性意义也十分明确的数据结构。留神，这个构造是与数据表相匹配的立体构造，不含 children 子集。 ...