package cc.mrbird.febs.common.tree;
|
|
import cn.hutool.core.collection.CollUtil;
|
import lombok.extern.slf4j.Slf4j;
|
|
import java.util.ArrayDeque;
|
import java.util.List;
|
|
/**
|
*
|
*
|
* @author wzy
|
* @date 2023-04-18
|
**/
|
@Slf4j
|
public class MatrixTree {
|
|
private static final MatrixTree MATRIX_TREE = new MatrixTree();
|
public static MatrixTree getInstance() {
|
return MATRIX_TREE;
|
}
|
|
private int childNodeCnt = 3;
|
|
// 节点数量
|
private int count = 0;
|
private MemberNode root;
|
|
private MatrixTree() {
|
count = 1;
|
}
|
|
/**
|
* @param node 待添加的节点
|
* @return 返回父节点
|
*/
|
public MemberNode addNode(MemberNode node) {
|
if (root == null) {
|
root = node;
|
return null;
|
}
|
|
MemberNode childTreeRoot = getNode(node.getRefererId());
|
|
MemberNode parentNode = findNotWholeNode(childTreeRoot == null ? root : childTreeRoot);
|
parentNode.addNode(node);
|
return parentNode;
|
}
|
|
public MemberNode addNode(MemberNode node, Long parentNodeId) {
|
if (parentNodeId == null) {
|
root = node;
|
return null;
|
}
|
|
MemberNode parentNode = getNode(parentNodeId);
|
parentNode.addNode(node);
|
return parentNode;
|
}
|
|
/**
|
* 层级遍历，查到子节点未满3个的节点
|
* @return
|
*/
|
public MemberNode findNotWholeNode(MemberNode root) {
|
ArrayDeque<MemberNode> deque = new ArrayDeque<>();
|
deque.add(root);
|
|
MemberNode result = null;
|
while(!deque.isEmpty()) {
|
int num = deque.size();
|
|
for (int i = 0; i < num; i++) {
|
MemberNode memberNode = deque.removeFirst();
|
if (memberNode.CHILD.size() < childNodeCnt) {
|
result = memberNode;
|
break;
|
}
|
|
for (MemberNode node : memberNode.CHILD) {
|
deque.addLast(node);
|
}
|
}
|
|
if (result != null) {
|
break;
|
}
|
}
|
|
return result;
|
}
|
|
public MemberNode findNotWholeNode() {
|
return findNotWholeNode(root);
|
}
|
|
/**
|
* 查找整个树下对应节点
|
* @param param memberId/address/inviteId
|
* @return
|
*/
|
public MemberNode getNode(Object param) {
|
if (root == null) {
|
return null;
|
}
|
|
if (root.getMemberId().equals(param) || root.getPhone().equals(param) || root.getInviteId().equals(param)) {
|
return root;
|
}
|
|
return getNode(root.CHILD, param);
|
}
|
|
/**
|
* 查找某节点下的对应节点
|
*
|
* @param nodeList 某节点
|
* @param param memberId/address/inviteId
|
* @return
|
*/
|
public MemberNode getNode(List<MemberNode> nodeList, Object param) {
|
if (CollUtil.isEmpty(nodeList)) {
|
return null;
|
}
|
|
for (MemberNode node : nodeList) {
|
if (node.getMemberId().equals(param) || node.getPhone().equals(param) || node.getInviteId().equals(param)) {
|
return node;
|
}
|
|
MemberNode childNode = getNode(node.CHILD, param);
|
if (childNode != null) {
|
return childNode;
|
}
|
}
|
|
return null;
|
}
|
}
|
