树的笔记()、拓扑结构

树是一个非常大的课题，光是概念就能弄的人头昏脑胀。 但是如果掌握了，是有点小小的成就感的。
树结构是应用非常广泛的结构，甚至可以说无处不在。
电脑里的文件夹是不是树结构，省市区县镇乡村是不是树结构，菜单是不是树结构，军队是不是树结构，职位是不是树结构。。。太多了，数都数不过来。

但是从数据库或代码的层面实现，里面的东西就太多了。

数据结构-树

树特点：

1、一个节点，即只有根节点，也可以是一棵树；
2、其中任何一个节点与下面所有节点构成的树成为子树；
3、根节点没有父节点，而叶子节点没有子节点；
4、除根节点外，任何节点有且仅有一个父节点；
5、任何节点可以有0～n个字节点。

平衡二叉树

1、树的左右高度差不能超过1；
2、任何往下递归的左子树和右子树，必须符合第一条性质；
3、没有任何节点的空树或只有根节点的树也是平衡二叉树。

二叉查找树

1、在任何递归子树中，左节点一定在右节点之前遍历；
2、前序，中序，后序，仅指根节点在遍历的位置顺序；

AVL树

一种平衡二叉查找树，增加和删除节点后，通过通过旋转重新达到平衡。

红黑树

1、节点只能是红色或者黑色；
2、根节点必须是黑色；
3、所有NIL节点都是黑色；
4、一条路径上不能出现相邻的两个红色节点；
5、在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

红黑树和AVL树的比较

黑深度：当前节点到NIL途径的黑色节点个数。

b-树(注 读作b树，不是b减树，没有减号这个概念)

b-树 就是 b树。

B树也翻译为B-树(是一种多路搜索树 并不是二叉的)
1、定义任意非叶子结点最多只有M个儿子；且M>2；
2、根结点的儿子数为[2, M]；
3、除根结点以外的非叶子结点的儿子数为[M/2, M]；
4、每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5、非叶子结点的关键字个数=指向儿子的指针个数-1；
6、非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7、非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8、所有叶子结点位于同一层；

b树是二叉树吗?

b树不是二叉树，因为二叉树每个节点最多有两个子节点，但是b树可以有多个子节点。
但是百度文档第一行居然是b树是二叉树。。。(感觉是写错了)

b+树的特点

相对于B树，B+树有四点不同：

1、B+树中非叶子节点不存放数据，存的是索引，它的叶子节点才存放数据，而B树中所有节点都存放数据；
2、B+树相邻的叶子节点之间通过链表指针连接起来，而B树没有；
3、查找过程中，B树在找到具体的数据以后就结束，而B+树则需要通过索引找到叶子节点中数据才结束；
4、B树任何一个关键字只出现在一个节点中，而B+树可以出现多次。

因此，相对于B树，B+树有以下优点：
1、非叶子节点不存放数据，单一节点存储更多的元素，磁盘IO次数更少；
2、查询都要找到叶子节点，查询性能稳定；
3、所有叶子节点形成有序链表，便于范围查询，查询效率更高。

b+树应用在哪些场景呢?
mysql数据库。

B树还是B+树，别再傻傻分不清了 # 这篇文章不错

二叉树可以简称读作b树吗?

不能，按照习惯，英文开头大写字母抽出来读是可以的，但是这里不行。
二叉树(binary tree)
平衡树(balance tree) # b树
二叉查找树(binary search tree) # bst

b树表示的是平衡树。
所以二叉树只有两种叫法，二叉树或binary tree。

b树和红黑树的区别

特性	红黑树	B树
基本结构	二叉搜索树（每个节点最多2个子节点）	多路搜索树（每个节点可有多于2个子节点）
平衡方式	通过颜色约束和旋转保持近似平衡	通过节点分裂/合并保持严格平衡
高度	较高（O(log n)）	较矮（O(log_m n)，m为阶数）
典型应用	内存数据结构（如C++ STL map/set）	磁盘/数据库索引（如文件系统、数据库）
节点存储	存储键值对，通常每个节点存一个键	存储键值对，每个节点可存多个键

b+树和b树的区别

特性	B树	B+树
数据存储位置	所有节点均可存储数据	仅叶子节点存储数据，内部节点只存键（索引）
叶子节点结构	叶子节点独立，无链表连接	叶子节点通过指针串联成有序链表
查询稳定性	不稳定（数据可能在中间节点找到）	稳定（必须到叶子节点）
范围查询效率	较低（需中序遍历）	极高（链表顺序访问）
内部节点结构	存储键+数据指针	仅存储键（索引）
空间利用率	相对较低	更高（键更密集）

总结：
1、b+树非叶子节点只存储索引，叶子节点只存储数据。 # 遍历时好遍历，只需遍历叶子节点
2、b+树叶子节点间有链表 # 便于范围查询

什么叫自平衡树?

菜单数据库设计

菜单结构主要的就是id,pid,type(菜单类型)。
关键就在怎么拾掇这堆id,pid上。

什么结构便于使用

正常来说，查出的结构一定是个map，完美的展现层级结构。
但是发现没有，map结构虽然全面，但是如果我想要查询某个按钮?
是不是不好查，估计要解map了，太费劲。

易于展现的结构，不一定易于查询。所以这里换个思路，还是map结构，但是以末级节点作为key，上级节点的集合以数组的形式顺序存放。
如：

{"crm":{"8888":[100,130,139],"9999":[100,130,914]}}

这样用起来就非常方便了。

获取树的方法

方法太多了，百度上代码一堆。

递归调用获取树

实测可用，没看懂这段代码什么意思。 递归不好把控执行流程。
后来加了日志大概明白了，先循环，匹配到id从list中删除，剩余list中以当前id作为pid继续递归。递归完毕后，resultList再统一添加。

publicstaticList<Resource>getTree(List<Resource>resources,Longid){if(StrUtils.isEmptyList(resources)){returnnull;}List<Resource>list=newArrayList<>();List<Resource>listContinue=newArrayList<>(resources);for(Resourceitem:resources){if(item.getPid().equals(id)){listContinue.remove(item);item.setChildren(getTree(listContinue,item.getId()));list.add(item);}}if(CollectionUtils.isEmpty(list)){returnnull;}else{returnlist;}}

一个节点是树吗?

可以是树，树可以只有一个节点。

正向树和反向树结合确定调用链

是这样，某个功能在哪些位置被调用，以及有哪些下级功能。
类似于idea的下级及引用。
实际上实现起来并不难，用两棵树就可以实现。

注：这里树比超链接强大多了，例如多个子级，excel就做不到，或者需要多行，即使实现了也不太优雅。

图和二叉树最大的区别是什么

树的上级节点是唯一的，最多有一个。
图的顶点(图没有节点的概念)是多对多的关系，并且所有顶点都是平等的，无所谓谁是父，谁是子。

拓扑结构(topological)

代码：

importjava.util.*;publicclassKahnAlgorithm{/** * Kahn 算法核心逻辑 * @param numNodes 节点总数 * @param adjacencyList 邻接表 (记录每个节点的下游依赖) * @param inDegrees 入度数组 (记录每个节点的前置依赖数量) * @return 拓扑排序后的节点列表，若存在环则返回空列表 */publicstaticList<Integer>topologicalSort(intnumNodes,List<List<Integer>>adjacencyList,int[]inDegrees){// 1. 将所有入度为 0 的节点（无前置依赖）加入队列Queue<Integer>queue=newLinkedList<>();for(inti=0;i<numNodes;i++){if(inDegrees[i]==0){queue.offer(i);}}List<Integer>result=newArrayList<>();// 2. 循环处理队列中的节点while(!queue.isEmpty()){intcurrentNode=queue.poll();result.add(currentNode);// 将当前节点加入最终排序结果// 3. 遍历当前节点的所有下游节点，将它们的入度减 1for(intneighbor:adjacencyList.get(currentNode)){inDegrees[neighbor]--;// 4. 如果某个下游节点的入度变成了 0，说明它的前置条件已全部满足，加入队列if(inDegrees[neighbor]==0){queue.offer(neighbor);}}}// 5. 环检测：如果结果列表的大小不等于节点总数，说明图中存在环if(result.size()!=numNodes){System.err.println("错误：检测到循环依赖，无法完成拓扑排序！");returnCollections.emptyList();}returnresult;}publicstaticvoidmain(String[]args){// 模拟主数据同步依赖：0-部门, 1-员工, 2-薪酬, 3-绩效// 依赖关系：部门(0) -> 员工(1) -> 薪酬(2)// 部门(0) -> 员工(1) -> 绩效(3)intnumNodes=4;// 构建邻接表List<List<Integer>>adjacencyList=newArrayList<>();for(inti=0;i<numNodes;i++){adjacencyList.add(newArrayList<>());}adjacencyList.get(0).add(1);// 0 -> 1adjacencyList.get(1).add(2);// 1 -> 2adjacencyList.get(1).add(3);// 1 -> 3// 构建入度数组 (0:部门, 1:员工, 2:薪酬, 3:绩效)int[]inDegrees={0,1,1,1};// 执行拓扑排序List<Integer>sortedOrder=topologicalSort(numNodes,adjacencyList,inDegrees);// 打印结果if(!sortedOrder.isEmpty()){System.out.println("主数据同步推荐执行顺序:");for(inti=0;i<sortedOrder.size();i++){System.out.print(sortedOrder.get(i));if(i<sortedOrder.size()-1)System.out.print(" -> ");}System.out.println();}}}

拓扑结构和循环遍历树的区别

对比维度	你提供的代码(递归构建树)	拓扑排序(Topological Sort)
核心目的	将扁平数据组装成父子层级结构(Tree)	将依赖关系解析成线性执行序列(List)
适用场景	前端渲染菜单、部门树、分类导航	主数据同步、ETL任务调度、工程工序
数据结构	必须是无环的树(Tree)	有向无环图(DAG，允许一个节点有多个父节点)
输出结果	嵌套的 JSON 对象(包含 children)	扁平的、有先后顺序的列表

拓扑结构和循环遍历树哪个更好呢?

他们不是竞争的关系，而是相辅相成的关系。

在主数据同步的完整链路中，这两个算法并不是"二选一"的竞争对手，而是上下游配合的搭档。

简单来说：拓扑排序是"总指挥"，递归/Map构建树是"包装工"。

1、拓扑排序：决定"什么时候同步"(调度层)
在主数据同步的调度层，必须使用拓扑排序。
作用：它负责解析你系统中所有主数据实体(如：国家、省份、城市、公司、部门、员工)之间的依赖关系，排出一个绝对安全的执行队列。
场景：确保在同步"员工"之前，"部门"一定已经同步完毕；在同步"部门"之前，"公司"一定已经同步完毕。
为什么必须用它：如果不用拓扑排序，一旦下游系统收到"员工"数据时，"部门"还没落库，就会因为外键约束导致同步大批量报错。

2、递归/Map构建树：决定"同步过去长什么样"(数据组装层)
当拓扑排序决定了"现在轮到同步部门了"，在数据组装层，就需要用到构建树的逻辑。
作用：将数据库里扁平的部门数据，组装成下游系统需要的层级结构。
场景：
场景 A(下游需要扁平数据)：如果下游是普通业务表，直接同步扁平的 List 即可，不需要构建树。
场景 B(下游需要树形数据)：如果下游是 OA 系统、钉钉，或者前端需要渲染组织架构菜单，你就必须把扁平数据组装成带有 children 的树形 JSON，此时才需要调用构建树的逻辑。