From e1114bf474d183b8ce985b2c4772ffe2d81397b6 Mon Sep 17 00:00:00 2001
From: Hentua <wangdoubleone@gmail.com>
Date: Tue, 18 Apr 2023 17:59:52 +0800
Subject: [PATCH] 添加三叉树逻辑

---
 src/main/java/cc/mrbird/febs/common/tree/MatrixTree.java |  115 ++++++++++++++++++++++++++++
 src/main/java/cc/mrbird/febs/common/tree/MemberNode.java |   37 +++++++++
 src/test/java/cc/mrbird/febs/TreeTest.java               |   30 +++++++
 3 files changed, 182 insertions(+), 0 deletions(-)

diff --git a/src/main/java/cc/mrbird/febs/common/tree/MatrixTree.java b/src/main/java/cc/mrbird/febs/common/tree/MatrixTree.java
new file mode 100644
index 0000000..7d7d263
--- /dev/null
+++ b/src/main/java/cc/mrbird/febs/common/tree/MatrixTree.java
@@ -0,0 +1,115 @@
+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 parentNode = findNotWholeNode();
+        parentNode.addNode(node);
+        return parentNode;
+    }
+
+    /**
+     * 层级遍历，查到子节点未满3个的节点
+     * @return
+     */
+    public MemberNode findNotWholeNode() {
+        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;
+    }
+
+    /**
+     * 查找整个树下对应节点
+     * @param param memberId/address/inviteId
+     * @return
+     */
+    public MemberNode getNode(Object param) {
+        if (root == null) {
+            return null;
+        }
+
+        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.getAddress().equals(param) || node.getInviteId().equals(param)) {
+                return node;
+            }
+
+            return getNode(node.CHILD, param);
+        }
+
+        return null;
+    }
+}
diff --git a/src/main/java/cc/mrbird/febs/common/tree/MemberNode.java b/src/main/java/cc/mrbird/febs/common/tree/MemberNode.java
new file mode 100644
index 0000000..c60e421
--- /dev/null
+++ b/src/main/java/cc/mrbird/febs/common/tree/MemberNode.java
@@ -0,0 +1,37 @@
+package cc.mrbird.febs.common.tree;
+
+import lombok.Data;
+
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * @author wzy
+ * @date 2022-08-23
+ **/
+@Data
+public class MemberNode {
+
+    private Long memberId;
+
+    private String address;
+
+    private String inviteId;
+
+    private String refererId;
+
+    public List<MemberNode> CHILD = new LinkedList<>();
+
+    public MemberNode(Long memberId, String address, String inviteId, String refererId) {
+        this.memberId = memberId;
+        this.address = address;
+        this.inviteId = inviteId;
+        this.refererId = refererId;
+    }
+
+    public MemberNode() {}
+
+    public void addNode(MemberNode node) {
+        this.CHILD.add(node);
+    }
+}
diff --git a/src/test/java/cc/mrbird/febs/TreeTest.java b/src/test/java/cc/mrbird/febs/TreeTest.java
new file mode 100644
index 0000000..28f5322
--- /dev/null
+++ b/src/test/java/cc/mrbird/febs/TreeTest.java
@@ -0,0 +1,30 @@
+package cc.mrbird.febs;
+
+import cc.mrbird.febs.common.tree.MatrixTree;
+import cc.mrbird.febs.common.tree.MemberNode;
+import lombok.extern.slf4j.Slf4j;
+import org.junit.jupiter.api.Test;
+import org.springframework.boot.test.context.SpringBootTest;
+
+/**
+ * @author wzy
+ * @date 2023-04-18
+ **/
+@Slf4j
+@SpringBootTest
+public class TreeTest {
+
+    @Test
+    public void treeTest() {
+        MatrixTree instance = MatrixTree.getInstance();
+        for (int i = 0; i < 20; i++) {
+            MemberNode node = new MemberNode();
+            node.setMemberId((long) i);
+            node.setInviteId(String.valueOf(i));
+            node.setAddress(String.valueOf(i));
+            instance.addNode(node);
+        }
+
+        System.out.println(111);
+    }
+}

--
Gitblit v1.9.1