fix:add matrixTree

Helius

2022-08-24 b90bb6e1cedd0210c231a5485b29c5724078d9f0

 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