`

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

Java数据结构 
阅读更多
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;
    }

}


三 实体OrganizationEntity 
package com.tree;

public class OrganizationEntity {
    public int parentId;
    public int orgId;
    public String orgName;
    public int getParentId() {
        return parentId;
    }
    public void setParentId(int parentId) {
        this.parentId = parentId;
    }
    public int getOrgId() {
        return orgId;
    }
    public void setOrgId(int orgId) {
        this.orgId = orgId;
    }
    public String getOrgName() {
        return orgName;
    }
    public void setOrgName(String orgName) {
        this.orgName = orgName;
    }
}
分享到：
| Java数据结构和算法--排序
评论
3 楼 qiuqinjun 2017-10-16  
有没有测试代码呢
2 楼 java-lxm 2014-04-22   

/* 找到一颗树中某个节点 */  
    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); //这里应该是child.getSelfId();吧 
                if (resultNode != null) {  
                    return resultNode;  
                }  
            }  
            return null;  
        }  
    }
1 楼 Fallen_Devil 2013-04-26  
十分清晰明了的代码。一开始看到注释非常少，觉得太可恶了，但是跟着逻辑跑了一下。咱瞬间震精了。。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    后序遍历多叉树.rar

    总的来说，理解和实现多叉树的后序遍历是C#程序员必备的技能之一，特别是在处理具有层次关系的数据或进行树形结构分析时。熟练掌握这些概念和技巧，能够帮助开发者更好地设计和优化他们的解决方案。

    自己用C语言实现的拓扑多叉树

    6. **打印多叉树**：为了可视化和调试，实现一个函数来按照某种格式打印树的结构。 7. **释放资源**：确保在完成操作后正确地释放所有分配的内存，防止内存泄漏。 C语言实现多叉树的优势在于其对底层内存管理的...

    Java实现多叉树查找

    - `TreeNode`类实现了`Serializable`接口，这意味着这个类的对象可以被序列化和反序列化。这在需要将对象持久化到磁盘或在网络上传输时非常有用。 2. **成员变量**： - `parentId`: 节点的父节点ID，用于建立节点...

    使用递归和dom遍历dom树形结构

    1. **主方法** (`main`): 初始化DOM解析器并解析指定的XML文件。 2. **处理文档方法** (`doc`): 获取文档的子节点列表，并调用`node`方法进行遍历。 3. **处理节点方法** (`node`): 遍历传入的节点列表。根据节点...

    java实现的二叉树的递归和非递归遍历

    在提供的"二叉树的递归和非递归遍历"压缩包文件中，可能包含了Java源代码，演示了如何实现这两种遍历方式。通过阅读和理解这些代码，你可以更好地掌握二叉树遍历的原理和实践，这对于理解和解决涉及二叉树的算法问题...

    java 迷宫 随机生成 自动寻找路径 用到树的深度遍历

    在这个项目中，我们将深入探讨如何使用Java来实现一个迷宫的随机生成以及自动寻找路径的方法，同时会涉及树的深度遍历这一核心算法。 首先，迷宫生成通常采用的是深度优先搜索（DFS，Depth-First Search）或广度...

    图的遍历和生成树求解实现课程设计

    根据给定文件的信息，我们可以将相关的知识点归纳如下： ...通过以上介绍，我们可以看到图的遍历算法和最小生成树的实现是计算机科学中的重要组成部分，它们不仅应用于理论研究，也在实际工程中有着广泛的应用。

    图的深度和广度遍历（Java实现）

    本篇将详细讲解如何使用Java实现图的深度优先遍历（DFS, Depth-First Search）和广度优先遍历（BFS, Breadth-First Search）。 1. **深度优先遍历（DFS）**： - DFS 是一种递归策略，它沿着某条路径深入到图的深处...

    多叉树结合JavaScript树形控件实现无限级树形结构（一种构建多级有序树形结构JSON（或XML）数据源的方法）

    2. Ext JS 框架：这是一种富客户端开发框架，其 TreePanel 组件常用于实现树形视图，支持 TreeNode 和 AsyncTreeNode，后者用于动态加载树节点。 3. 动态生成树节点：两种策略，一次性生成所有节点和逐级加载，前者...

    02-Java基础(数组-常见操作-遍历

    有两种主要方式来初始化数组：直接初始化和动态初始化。直接初始化时，我们可以在声明时同时指定数组的大小和初始值，如： ```java int[] numbers = {1, 2, 3, 4, 5}; ``` 而动态初始化则是在声明时仅指定数组长度，...

    Java实现遍历一个数组

    在Java编程语言中，遍历数组是常见的操作，无论是在数据处理、算法实现还是其他程序设计中都必不可少。本文将详细介绍如何使用Java来遍历数组，并通过实例代码和注释帮助理解这一过程。 首先，Java中的数组是一种...

    树或二元树的层次遍历

    - **层次遍历算法**：初始化队列，将根节点放入队列；循环处理队列，每次取出队列头部的节点，访问该节点，然后将其左右子节点（如果存在）依次入队，直到队列为空。 **系统实现：** 在实现阶段，需要编写代码来...

    决策树Java代码实现

    决策树的Java实现涉及多个关键概念和技术点，包括但不限于节点的定义、数据结构的选择、属性的选择等。通过上述分析，我们不仅了解了决策树的基本原理，还深入了解了其在Java中的具体实现方式。这对于理解和开发实际...

    Java目录树控件

    在`java实现系统目录树控件.txt`文件中，可能包含了实现这一功能的具体代码示例，包括如何初始化`JTree`，如何构建树模型，以及如何处理用户交互等。通过阅读和理解这段代码，开发者可以更好地掌握如何在实际项目中...

    树，二叉树及其遍历，哈夫曼树课题讲解

    1. 初始化和销毁树。 2. 创建树，根据给定的规则生成树结构。 3. 清除树，释放内存。 4. 判断树是否为空。 5. 获取树的深度。 6. 访问根节点、双亲节点、子节点。 7. 插入和删除子节点。 8. 遍历树，如前序、中序、...

    图的创立数据结构对其进行深度优先遍历和广度优先遍历

    在本文中，我们将深入探讨图的数据结构以及如何对图进行深度优先遍历（DFS）和广度优先遍历（BFS）。首先，我们要理解图的基本概念。图是一种数据结构，用于表示对象之间的关系，其中的对象称为顶点或节点，而它们...

    树的深度和广度遍历C++源程序

    本段代码展示了如何用C++实现树的深度优先遍历和广度优先遍历。虽然实际实现的是图的遍历，但原理和树的遍历非常相似，这里我们将其理解为树的遍历。 1. **数据结构定义**： - `const int MAX_VERTEX_NUM = 10;`：...

    vc实现树形目录遍历

    在VC++（Visual C++）开发环境中，实现树形目录遍历是一项常见的任务，尤其在文件管理系统或资源浏览器等应用中。本知识点将详细讲解如何使用递归算法来完成这一功能，以及涉及到的相关编程概念。 首先，理解目录...

    tree_反向层次遍历树_4321_

    "tree_反向层次遍历树_4321_"这个标题指的是一个特定的树遍历方法，即反向层次遍历（也称为反向深度优先搜索）。在标准的层次遍历（通常是从根节点开始，按照从上至下、从左至右的顺序访问节点）中，反向层次遍历则...

    层次遍历多元树（在文件tree.cpp中3个空）、先根遍历、后根遍历的递归函数

    总结来说，层次遍历、先根遍历和后根遍历是树遍历的三种基本方式，它们在不同的场景下各有优势。在实际编程中，理解这些遍历方法的递归实现至关重要，因为它们可以用来解决各种问题，例如搜索、序列化/反序列化树等...

Magicbox
Global site tag (gtag.js) - Google Analytics