Java多叉树的生成初始化和遍历以及查找

  1. 云栖社区>
  2. 博客>
  3. 正文

Java多叉树的生成初始化和遍历以及查找

心月狐 2018-09-25 11:39:13 浏览3150
展开阅读全文

/**
 * 〈一句话功能简述〉<br> 
 * 〈属性〉
 *
 * @author zhoumoxuan
 * @create 8/22/18
 * @since 1.0.0
 */
public class Test {
    private int id;
    private int pid;
    private String name;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getPid() {
        return pid;
    }

    public void setPid(int pid) {
        this.pid = pid;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}


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

/**
 * 〈一句话功能简述〉<br>
 * 〈树形结构〉
 *
 * @author zhoukai7
 * @create 8/22/18
 * @since 1.0.0
 */
public class TreeNode implements Serializable {
    private int parentId;//父亲ID
    private int ownId;//孩子ID
    protected String nodeName;//节点名称
    protected TreeNode parentNode;
    protected List<TreeNode> childList;

    /**
     * 必须进程初始化否则会抛出异常
     */
    public TreeNode() {
        initChildList();
    }

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

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

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

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

    }

    /**
     * 判断是否是有效的节点
     *
     * @return
     */
    public boolean isValidTree() {
        return true;
    }

    /**
     * 返回当前节点的父辈级别的节点列表
     *
     * @return
     */
    public List<TreeNode> getElders() {
        List<TreeNode> elderList = new ArrayList<TreeNode>();
        TreeNode parentNode = this.getParentNode();
        if (parentNode == null) {
            return elderList;
        } else {
            elderList.add(parentNode);
            elderList.addAll(parentNode.getElders());
            return elderList;
        }
    }

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

    /**
     * 返回当前节点的所有的孩子
     *
     * @return
     */
    public List<TreeNode> getChildList() {
        return childList;
    }

    /**
     * 删除当前节点和它的子孙
     */
    public void deleteNode() {
        TreeNode parentNode = this.getParentNode();
        int id = this.getOwnId();

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

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

    /**
     * 当前节点中插入新节点
     *
     * @param treeNode
     * @return
     */
    public boolean insertNewNode(TreeNode treeNode) {
        int newParentId = treeNode.getParentId();
        //如果相等则新增加list保存该节点
        if (this.parentId == newParentId) {
            addChildNode(treeNode);
            return true;
        } else {
            List<TreeNode> childList = this.getChildList();
            int size = childList.size();
            boolean flag;
            //如果不存在则需要从该节点的子节点列表循环查找
            for (int i = 0; i < size; i++) {
                TreeNode childNode = childList.get(i);
                flag = childNode.insertNewNode(treeNode);
                if (flag == true) {
                    return true;
                }

            }
            return false;
        }
    }

    /**
     * 查找树中某个节点
     *
     * @param id
     * @return
     */
    public TreeNode findTreeNodeById(int id) {
        if (this.ownId == id) {
            return this;
        }

        if (childList.isEmpty() || childList == null) {
            return null;
        } else {
            int size = childList.size();
            for (int i = 0; i < size; i++) {
                TreeNode child = childList.get(i);
                TreeNode result = child.findTreeNodeById(id);
                if (result != null) {
                    return result;
                }
            }
            return null;
        }
    }

    /**
     * 遍历树
     */
    public void traverseTree() {
        if (ownId < 0) {
            return;
        }
        if (childList == null || childList.isEmpty()) {
            return;
        }

        int size = childList.size();
        for (int i = 0; i < size; i++) {
            TreeNode child = childList.get(i);
            child.traverseTree();
        }
    }


    /**
     * 遍历树同时保存该节点中的parentNode属性
     *
     * @param treeNode
     */
    public void traverseTreeAndSaveParentNode(TreeNode treeNode) {
        if (ownId < 0) {
            return;
        }
        if (childList == null || childList.isEmpty()) {
            return;
        }

        int size = childList.size();
        for (int i = 0; i < size; i++) {
            TreeNode child = childList.get(i);
            //treeNode.getChildList().clear();//此处可以清除数据如果嫌冗余
            child.setParentNode(treeNode);
            child.traverseTreeAndSaveParentNode(child);
        }
    }


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

    public int getParentId() {
        return parentId;
    }

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

    public int getOwnId() {
        return ownId;
    }

    public void setOwnId(int ownId) {
        this.ownId = ownId;
    }

    public TreeNode getParentNode() {
        return parentNode;
    }

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

    public String getNodeName() {
        return nodeName;
    }

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

}

/**
 * 〈一句话功能简述〉<br> 
 * 〈树形工具类〉
 *
 * @author zhoukai7
 * @create 8/22/18
 * @since 1.0.0
 */
import java.util.List;
import java.util.Iterator;
import java.util.HashMap;

public class TreeNodeUtil {
    private TreeNode root;
    private List<TreeNode> nodeList;
    private boolean isValidTree = true;

    public TreeNodeUtil() {
    }

    public TreeNodeUtil(List<TreeNode> treeNodeList) {
        nodeList = treeNodeList;
        createTree();
    }

    public static TreeNode getTreeNodeById(TreeNode tree, int id) {
        if (tree == null) {
            return null;
        }

        TreeNode treeNode = tree.findTreeNodeById(id);
        return treeNode;
    }

    /**
     * 从给定的treeNode或实体列表中生成一个树
     */
    public void createTree() {
        HashMap nodeMap = traverseNodeToMap();
        relevancyNodeToMap(nodeMap);
    }

    /**
     * 便利list保存node节点到Map中
     */
    protected HashMap traverseNodeToMap() {
        int maxId = Integer.MAX_VALUE;
        HashMap nodeMap = new HashMap<String, TreeNode>();
        Iterator it = nodeList.iterator();
        while (it.hasNext()) {
            TreeNode treeNode = (TreeNode) it.next();
            int id = treeNode.getOwnId();
            if (id < maxId) {
                maxId = id;
                this.root = treeNode;
            }
            String keyId = String.valueOf(id);

            nodeMap.put(keyId, treeNode);
        }
        return nodeMap;
    }

    /**
     * 把list中的TreeNode进行父亲孩子节点互相关联
     */
    protected void relevancyNodeToMap(HashMap nodeMap) {
        Iterator it = nodeMap.values().iterator();
        while (it.hasNext()) {
            TreeNode treeNode = (TreeNode) it.next();
            int parentId = treeNode.getParentId();
            String parentKeyId = String.valueOf(parentId);
            if (nodeMap.containsKey(parentKeyId)) {
                TreeNode parentNode = (TreeNode) nodeMap.get(parentKeyId);
                if (parentNode == null) {
                    this.isValidTree = false;
                    return;
                } else {
                    //这里需要把父亲节点做关联用于查找使用
                    parentNode.addChildNode(treeNode);
                }
            }
        }
    }


    /**
     * 判断是否有效的树
     */
    public boolean isValidTree() {
        return this.isValidTree;
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public List<TreeNode> getNodeList() {
        return nodeList;
    }

    public void setNodeList(List<TreeNode> nodeList) {
        this.nodeList = nodeList;
    }
}



import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br> 
 * 〈测试类〉
 *
 * @author zhoumoxuan
 * @create 8/22/18
 * @since 1.0.0
 */
public class TestTree {

    public static void main(String[] args){
        //获取业务list数据
        List<Test> listAll = null;
        //new一个list保存全部节点
        List<TreeNode> listNode = new ArrayList<TreeNode>();
        //2、必须初始化一个root节点,保证根的唯一性
        TreeNode treeNode2 = new TreeNode();
        treeNode2.setParentId(0);
        treeNode2.setOwnId(0);
        treeNode2.setNodeName("root");
        listNode.add(treeNode2);

        //3、循环遍历所有
        for (int j = 0; j < listAll.size(); j++) {

            Test sysDeptEntity = listAll.get(j);
            TreeNode treeNode = new TreeNode();
            treeNode.setParentId(sysDeptEntity.getPid());
            treeNode.setOwnId(sysDeptEntity.getId());
            treeNode.setNodeName(sysDeptEntity.getName());
            listNode.add(treeNode);
        }

        //4、绑定父节点跟子节点的关系
        TreeNodeUtil treeHelper = new TreeNodeUtil(listNode);
        TreeNode treeNode = treeHelper.getRoot();
        // 这里默认生成了一次多余的root子节点,必须执行删除
        treeNode.deleteChildNode(0);
        treeNode.traverseTreeAndSaveParentNode(treeNode);
        //获取树形
        TreeNode treeNode4 = treeHelper.getRoot();

    }

}


网友评论

登录后评论
0/500
评论
心月狐
+ 关注