From b90bb6e1cedd0210c231a5485b29c5724078d9f0 Mon Sep 17 00:00:00 2001
From: Helius <wangdoubleone@gmail.com>
Date: Wed, 24 Aug 2022 17:14:38 +0800
Subject: [PATCH] fix:add matrixTree
---
src/main/java/cc/mrbird/febs/tree/MatrixTree.java | 115 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 114 insertions(+), 1 deletions(-)
diff --git a/src/main/java/cc/mrbird/febs/tree/MatrixTree.java b/src/main/java/cc/mrbird/febs/tree/MatrixTree.java
index 259294f..deea01b 100644
--- a/src/main/java/cc/mrbird/febs/tree/MatrixTree.java
+++ b/src/main/java/cc/mrbird/febs/tree/MatrixTree.java
@@ -1,16 +1,30 @@
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() {}
+ public MatrixTree() {
+ count = 1;
+ }
public MatrixTree(MemberNode root) {
count = 1;
@@ -22,6 +36,105 @@
}
/**
+ * 添加节点到树中
+ * 先判断该节点的直推荐人是否在树中，若在则判断该推荐人的矩阵是否完成，若未完成则添加到该矩阵中，若已完成，则完善整个树
+ * 如果直推荐人没有在树中，则直接添加到树
+ *
+ * @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
--
Gitblit v1.9.1