package cc.mrbird.febs.tree;
|
|
import com.sun.jmx.remote.internal.ArrayQueue;
|
import lombok.extern.slf4j.Slf4j;
|
|
import java.util.ArrayDeque;
|
import java.util.Queue;
|
|
/**
|
* @author wzy
|
* @date 2022-08-23
|
**/
|
@Slf4j
|
public class MatrixTree {
|
|
private static final MatrixTree matrixTree = new MatrixTree();
|
public static MatrixTree getInstance() {
|
return matrixTree;
|
}
|
|
// 节点数量
|
private int count = 0;
|
private MemberNode root;
|
|
public MatrixTree() {
|
count = 1;
|
}
|
|
public MatrixTree(MemberNode root) {
|
count = 1;
|
this.root = root;
|
}
|
|
public int getCount() {
|
return count;
|
}
|
|
/**
|
* 添加节点到树中
|
* 先判断该节点的直推荐人是否在树中，若在则判断该推荐人的矩阵是否完成，若未完成则添加到该矩阵中，若已完成，则完善整个树
|
* 如果直推荐人没有在树中，则直接添加到树
|
*
|
* @param node 待添加的节点
|
* @return 返回父节点
|
*/
|
public MemberNode addNode(MemberNode node) {
|
if (root == null) {
|
root = node;
|
return null;
|
}
|
|
count++;
|
|
MemberNode parent = getNode(node.getRefererId());
|
MemberNode memberNode = null;
|
if (parent != null) {
|
memberNode = wholeMatrix(parent, node, 2, 1);
|
}
|
|
if (memberNode != null) {
|
return memberNode;
|
}
|
|
MemberNode notWholeNode = getNotWholeNode();
|
if (notWholeNode.getLeft() == null) {
|
notWholeNode.setLeft(node);
|
} else {
|
notWholeNode.setRight(node);
|
}
|
|
return notWholeNode;
|
}
|
|
/**
|
* 通过层级遍历，依次获取没有完整左右子节点的节点
|
*
|
* @return
|
*/
|
public MemberNode getNotWholeNode() {
|
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.getLeft() == null || memberNode.getRight() == null) {
|
result = memberNode;
|
break;
|
}
|
|
deque.addLast(memberNode.getLeft());
|
deque.addLast(memberNode.getRight());
|
}
|
|
if (result != null) {
|
break;
|
}
|
}
|
return result;
|
}
|
|
/**
|
* 将节点添加到矩阵。若矩阵已完成，直接返回null
|
*
|
* @param node 矩阵root节点
|
* @param newNode 待添加的节点
|
* @param depth 矩阵深度(目前为2)
|
* @param index 当前所有深度
|
* @return
|
*/
|
public MemberNode wholeMatrix(MemberNode node, MemberNode newNode, int depth, int index) {
|
if (node.getLeft() == null) {
|
node.setLeft(newNode);
|
return node;
|
}
|
|
if (node.getRight() == null) {
|
node.setRight(newNode);
|
return node;
|
}
|
|
if (index >= depth) {
|
return null;
|
}
|
|
MemberNode left = wholeMatrix(node.getLeft(), newNode, depth, index + 1);
|
if (left != null) {
|
return left;
|
}
|
|
return wholeMatrix(node.getRight(), newNode, depth, index + 1);
|
}
|
|
/**
|
* 查找整个树下对应节点
|
* @param param memberId/address/inviteId
|
* @return
|
*/
|
public MemberNode getNode(Object param) {
|
return getNode(root, param);
|
}
|
|
/**
|
* 查找某节点下的对应节点
|
*
|
* @param node 某节点
|
* @param param memberId/address/inviteId
|
* @return
|
*/
|
public MemberNode getNode(MemberNode node, Object param) {
|
if (node == null) {
|
return null;
|
}
|
|
if (node.getMemberId().equals(param) || node.getAddress().equals(param) || node.getInviteId().equals(param)) {
|
return node;
|
}
|
|
MemberNode leftNode = getNode(node.getLeft(), param);
|
if (leftNode != null) {
|
return leftNode;
|
}
|
|
return getNode(node.getRight(), param);
|
}
|
}
|
