添加三叉树逻辑

Hentua

2023-04-18 e1114bf474d183b8ce985b2c4772ffe2d81397b6

添加三叉树逻辑

 src/main/java/cc/mrbird/febs/common/tree/MatrixTree.java

New file
@@ -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;
    }
}

 src/main/java/cc/mrbird/febs/common/tree/MemberNode.java

New file
@@ -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);
    }
}

 src/test/java/cc/mrbird/febs/TreeTest.java

New file
@@ -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);
    }
}