【JAVA】一个简单的多叉树

全面解析 Coco AI，一款开源、免费的智能搜索与知识库工具

package NTree;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class NTreeNode implements Serializable {

	private static final long serialVersionUID = 1615973232860200623L;
	
	private int parentId;
    private int selfId;
    protected String nodeName;
    protected NTreeNode parentNode;
    protected List<NTreeNode> childList;

    public NTreeNode() {
        initChildList();
    }

    public NTreeNode(NTreeNode parentNode) {
        this.getParentNode();
        initChildList();
    }

    public boolean isLeaf() {
        if (childList == null) {
            return true;
        } else {
            if (childList.isEmpty()) {
                return true;
            } else {
                return false;
            }
        }
    }

    /* 插入一个child节点到当前节点中 */
    public void addChildNode(NTreeNode treeNode) {
        initChildList();
        childList.add(treeNode);
    }

    public void initChildList() {
        if (childList == null)
            childList = new ArrayList<NTreeNode>();
    }

    public boolean isValidTree() {
        return true;
    }

    /* 返回当前节点的父辈节点集合 */
    public List<NTreeNode> getElders() {
        List<NTreeNode> elderList = new ArrayList<NTreeNode>();
        NTreeNode parentNode = this.getParentNode();
        if (parentNode == null) {
            return elderList;
        } else {
            elderList.add(parentNode);
            elderList.addAll(parentNode.getElders());
            return elderList;
        }
    }

    /* 返回当前节点的晚辈集合 */
    public List<NTreeNode> getJuniors() {
        List<NTreeNode> juniorList = new ArrayList<NTreeNode>();
        List<NTreeNode> childList = this.getChildList();
        if (childList == null) {
            return juniorList;
        } else {
            int childNumber = childList.size();
            for (int i = 0; i < childNumber; i++) {
                NTreeNode junior = childList.get(i);
                juniorList.add(junior);
                juniorList.addAll(junior.getJuniors());
            }
            return juniorList;
        }
    }

    /* 返回当前节点的孩子集合 */
    public List<NTreeNode> getChildList() {
        return childList;
    }

    /* 删除节点和它下面的晚辈 */
    public void deleteNode() {
        NTreeNode parentNode = this.getParentNode();
        int id = this.getSelfId();

        if (parentNode != null) {
            parentNode.deleteChildNode(id);
        }
    }

    /* 删除当前节点的某个子节点 */
    public void deleteChildNode(int childId) {
        List<NTreeNode> childList = this.getChildList();
        int childNumber = childList.size();
        for (int i = 0; i < childNumber; i++) {
            NTreeNode child = childList.get(i);
            if (child.getSelfId() == childId) {
                childList.remove(i);
                return;
            }
        }
    }

    /* 动态的插入一个新的节点到当前树中 */
    public boolean insertJuniorNode(NTreeNode treeNode) {
        int juniorParentId = treeNode.getParentId();
        if (this.parentId == juniorParentId) {
            addChildNode(treeNode);
            return true;
        } else {
            List<NTreeNode> childList = this.getChildList();
            int childNumber = childList.size();
            boolean insertFlag;

            for (int i = 0; i < childNumber; i++) {
                NTreeNode childNode = childList.get(i);
                insertFlag = childNode.insertJuniorNode(treeNode);
                if (insertFlag == true)
                    return true;
            }
            return false;
        }
    }

    /* 找到一颗树中某个节点 */
    public NTreeNode findNTreeNodeById(int id) {
        if (this.selfId == id)
            return this;
        if (childList.isEmpty() || childList == null) {
            return null;
        } else {
            int childNumber = childList.size();
            for (int i = 0; i < childNumber; i++) {
                NTreeNode child = childList.get(i);
                NTreeNode resultNode = child.findNTreeNodeById(id);
                if (resultNode != null) {
                    return resultNode;
                }
            }
            return null;
        }
    }

    /* 遍历一棵树，层次遍历 */
    public void traverse() {
        if (selfId < 0)
            return;
        print(this.selfId);
        if (childList == null || childList.isEmpty())
            return;
        int childNumber = childList.size();
        for (int i = 0; i < childNumber; i++) {
            NTreeNode child = childList.get(i);
            child.traverse();
        }
    }
    
    /**
     * 递归遍历
     * 如果树太深的话，会出现java.lang.StackOverflowError
     *
     * @param root
     */
    public static void recursion(NTreeNode root) {
        System.out.println(root.getNodeName());
        for (NTreeNode child : root.getChildList()) {
            recursion(child);
        }
    }

    /**
     * 广度优先需要构建一个先进先出的队列
     *
     * @param root
     */
    public static void breadthFirst(NTreeNode root) {
        Deque<NTreeNode> nodeDeque = new LinkedList<>();
        NTreeNode node = root;
        nodeDeque.add(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            System.out.println(node.getNodeName());
            nodeDeque.addAll(node.getChildList());
        }

    }
    
    /**
     * 深度优先需要构建一个后进先出的栈
     *
     * @param root
     */
    public static void depthFirst(NTreeNode root) {
        Deque<NTreeNode> nodeDeque = new LinkedList<>();
        NTreeNode node = root;
        nodeDeque.push(node);
        while (!nodeDeque.isEmpty()) {
            node = nodeDeque.pop();
            System.out.println(node.getNodeName());
            List<NTreeNode> children = node.getChildList();
            //注意这里要从后向前遍历
            for (int i = children.size() - 1; i >= 0; i--) {
                nodeDeque.push(children.get(i));
            }
        }
    }


    public void print(String content) {
        System.out.println(content);
    }

    public void print(int content) {
        System.out.println(String.valueOf(content));
    }

    public void setChildList(List<NTreeNode> childList) {
        this.childList = childList;
    }

    public int getParentId() {
        return parentId;
    }

    public void setParentId(int parentId) {
        this.parentId = parentId;
    }

    public int getSelfId() {
        return selfId;
    }

    public void setSelfId(int selfId) {
        this.selfId = selfId;
    }

    public NTreeNode getParentNode() {
        return parentNode;
    }

    public void setParentNode(NTreeNode parentNode) {
        this.parentNode = parentNode;
    }

    public String getNodeName() {
        return nodeName;
    }

    public void setNodeName(String nodeName) {
        this.nodeName = nodeName;
    }
}