java多叉树的实现类，完成树的初始化和遍历

Myth丶恋晨 2022-09-17 14:23 308阅读 0赞

在**[java][]**编程中，经常会用到创建树形结构的菜单或者目录结构，这就需要设计一个**树形**类，帮助实现类似功能。本文从其他地方摘抄了一个**多叉树**类设计，包括两个文件（TreeNode.java和TreeHelper.java）  TreeNode类完成树节点的数据结构，TreeHelper类通过输入一个TreeNode列表，生成一颗有一个树根的树！希望能有帮助。

一：树节点的定义（TreeNode.java）

package com.tree;
    
    import java.util.List;
    import java.util.ArrayList;
    import java.io.Serializable;
    
    public class TreeNode implements Serializable {
        private int parentId;
        private int selfId;
        protected String nodeName;
        protected Object obj;
        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节点到当前节点中 */
        public void addChildNode(TreeNode treeNode) {
            initChildList();
            childList.add(treeNode);
        }
    
        public void initChildList() {
            if (childList == null)
                childList = new ArrayList<TreeNode>();
        }
    
        public boolean isValidTree() {
            return true;
        }
    
        /* 返回当前节点的父辈节点集合 */
        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;
            }
        }
    
        /* 返回当前节点的晚辈集合 */
        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;
            }
        }
    
        /* 返回当前节点的孩子集合 */
        public List<TreeNode> getChildList() {
            return childList;
        }
    
        /* 删除节点和它下面的晚辈 */
        public void deleteNode() {
            TreeNode parentNode = this.getParentNode();
            int id = this.getSelfId();
    
            if (parentNode != null) {
                parentNode.deleteChildNode(id);
            }
        }
    
        /* 删除当前节点的某个子节点 */
        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.getSelfId() == childId) {
                    childList.remove(i);
                    return;
                }
            }
        }
    
        /* 动态的插入一个新的节点到当前树中 */
        public boolean insertJuniorNode(TreeNode treeNode) {
            int juniorParentId = treeNode.getParentId();
            if (this.parentId == juniorParentId) {
                addChildNode(treeNode);
                return true;
            } else {
                List<TreeNode> childList = this.getChildList();
                int childNumber = childList.size();
                boolean insertFlag;
    
                for (int i = 0; i < childNumber; i++) {
                    TreeNode childNode = childList.get(i);
                    insertFlag = childNode.insertJuniorNode(treeNode);
                    if (insertFlag == true)
                        return true;
                }
                return false;
            }
        }
    
        /* 找到一颗树中某个节点 */
        public TreeNode findTreeNodeById(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++) {
                    TreeNode child = childList.get(i);
                    TreeNode resultNode = child.findTreeNodeById(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++) {
                TreeNode child = childList.get(i);
                child.traverse();
            }
        }
    
        public void print(String content) {
            System.out.println(content);
        }
    
        public void print(int content) {
            System.out.println(String.valueOf(content));
        }
    
        public void setChildList(List<TreeNode> 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 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;
        }
    
        public Object getObj() {
            return obj;
        }
    
        public void setObj(Object obj) {
            this.obj = obj;
        }
    }

二：TreeHelper.java

package com.tree;
    
    import java.util.List;
    import java.util.Iterator;
    import java.util.ArrayList;
    import java.util.HashMap;
    
    public class TreeHelper {
    
        private TreeNode root;
        private List<TreeNode> tempNodeList;
        private boolean isValidTree = true;
    
        public TreeHelper() {
        }
    
        public TreeHelper(List<TreeNode> treeNodeList) {
            tempNodeList = treeNodeList;
            generateTree();
        }
    
        public static TreeNode getTreeNodeById(TreeNode tree, int id) {
            if (tree == null)
                return null;
            TreeNode treeNode = tree.findTreeNodeById(id);
            return treeNode;
        }
    
        /** generate a tree from the given treeNode or entity list */
        public void generateTree() {
            HashMap nodeMap = putNodesIntoMap();
            putChildIntoParent(nodeMap);
        }
    
        /**
         * put all the treeNodes into a hash table by its id as the key
         * 
         * @return hashmap that contains the treenodes
         */
        protected HashMap putNodesIntoMap() {
            int maxId = Integer.MAX_VALUE;
            HashMap nodeMap = new HashMap<String, TreeNode>();
            Iterator it = tempNodeList.iterator();
            while (it.hasNext()) {
                TreeNode treeNode = (TreeNode) it.next();
                int id = treeNode.getSelfId();
                if (id < maxId) {
                    maxId = id;
                    this.root = treeNode;
                }
                String keyId = String.valueOf(id);
    
                nodeMap.put(keyId, treeNode);
                // System.out.println("keyId: " +keyId);
            }
            return nodeMap;
        }
    
        /**
         * set the parent nodes point to the child nodes
         * 
         * @param nodeMap
         *            a hashmap that contains all the treenodes by its id as the key
         */
        protected void putChildIntoParent(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);
                        // System.out.println("childId: " +treeNode.getSelfId()+" parentId: "+parentNode.getSelfId());
                    }
                }
            }
        }
    
        /** initialize the tempNodeList property */
        protected void initTempNodeList() {
            if (this.tempNodeList == null) {
                this.tempNodeList = new ArrayList<TreeNode>();
            }
        }
    
        /** add a tree node to the tempNodeList */
        public void addTreeNode(TreeNode treeNode) {
            initTempNodeList();
            this.tempNodeList.add(treeNode);
        }
    
        /**
         * insert a tree node to the tree generated already
         * 
         * @return show the insert operation is ok or not
         */
        public boolean insertTreeNode(TreeNode treeNode) {
            boolean insertFlag = root.insertJuniorNode(treeNode);
            return insertFlag;
        }
    
        /**
         * adapt the entities to the corresponding treeNode
         * 
         * @param entityList
         *            list that contains the entities
         *@return the list containg the corresponding treeNodes of the entities
         */
        public static List<TreeNode> changeEnititiesToTreeNodes(List entityList) {
            OrganizationEntity orgEntity = new OrganizationEntity();
            List<TreeNode> tempNodeList = new ArrayList<TreeNode>();
            TreeNode treeNode;
    
            Iterator it = entityList.iterator();
            while (it.hasNext()) {
                orgEntity = (OrganizationEntity) it.next();
                treeNode = new TreeNode();
                treeNode.setObj(orgEntity);
                treeNode.setParentId(orgEntity.getParentId());
                treeNode.setSelfId(orgEntity.getOrgId());
                treeNode.setNodeName(orgEntity.getOrgName());
                tempNodeList.add(treeNode);
            }
            return tempNodeList;
        }
    
        public boolean isValidTree() {
            return this.isValidTree;
        }
    
        public TreeNode getRoot() {
            return root;
        }
    
        public void setRoot(TreeNode root) {
            this.root = root;
        }
    
        public List<TreeNode> getTempNodeList() {
            return tempNodeList;
        }
    
        public void setTempNodeList(List<TreeNode> tempNodeList) {
            this.tempNodeList = tempNodeList;
        }
    
    }

[java]: http://blog.csdn.net/shanzhizi/article/category/1428731