From 0c68494f50d375a046e6a9d07321860984a7f805 Mon Sep 17 00:00:00 2001
From: KKSU <15274802129@163.com>
Date: Thu, 13 Jun 2024 15:49:43 +0800
Subject: [PATCH] 星级矩阵

---
 src/main/java/cc/mrbird/febs/tree/MatrixTree.java |  144 +++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 142 insertions(+), 2 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..dbaa294 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 cn.hutool.core.util.RandomUtil;
+import cn.hutool.json.JSONUtil;
+import lombok.extern.slf4j.Slf4j;
+
+import java.util.ArrayDeque;
+
 /**
  * @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;
@@ -19,6 +33,105 @@
 
     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);
     }
 
     /**
@@ -42,7 +155,7 @@
             return null;
         }
 
-        if (node.getMemberId().equals(param) || node.getAddress().equals(param) || node.getInviteId().equals(param)) {
+        if (node.getFundId().equals(param) ||node.getMemberId().equals(param) || node.getAddress().equals(param) || node.getInviteId().equals(param)) {
             return node;
         }
 
@@ -53,4 +166,31 @@
 
         return getNode(node.getRight(), param);
     }
+
+    /**
+     * 移除树中节点
+     *
+     * @param param
+     */
+    public void remove(Object param) {
+    }
+
+    public static void main(String[] args) {
+        MatrixTree matrixTree = new MatrixTree();
+        String refererId = null;
+        for (int i = 0; i < 11; i++) {
+            String inviteId = RandomUtil.randomString(6);
+            if (i == 0) {
+                refererId = inviteId;
+            }
+            MemberNode memberNode = new MemberNode();
+            memberNode.setMemberId(Long.parseLong(i + 1 + ""));
+            memberNode.setInviteId(inviteId);
+            memberNode.setAddress(RandomUtil.randomString(14));
+            memberNode.setRefererId(refererId);
+            matrixTree.addNode(memberNode);
+        }
+        System.out.println(JSONUtil.parseObj(matrixTree));
+        System.out.println(System.currentTimeMillis());
+    }
 }

--
Gitblit v1.9.1