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;
}
}
分享到：
相关推荐
总的来说，理解和实现多叉树的后序遍历是C#程序员必备的技能之一，特别是在处理具有层次关系的数据或进行树形结构分析时。熟练掌握这些概念和技巧，能够帮助开发者更好地设计和优化他们的解决方案。
6. **打印多叉树**：为了可视化和调试，实现一个函数来按照某种格式打印树的结构。 7. **释放资源**：确保在完成操作后正确地释放所有分配的内存，防止内存泄漏。 C语言实现多叉树的优势在于其对底层内存管理的...
- `TreeNode`类实现了`Serializable`接口，这意味着这个类的对象可以被序列化和反序列化。这在需要将对象持久化到磁盘或在网络上传输时非常有用。 2. **成员变量**： - `parentId`: 节点的父节点ID，用于建立节点...
递归是一种函数调用自身的技术，常用于解决具有自相似性质的问题，如树遍历。在JavaScript中，遍历多叉树的递归方法通常包括以下步骤： 1. **定义遍历函数**：创建一个名为`traverseNode`的函数，该函数接收一个...
在提供的"二叉树的递归和非递归遍历"压缩包文件中，可能包含了Java源代码，演示了如何实现这两种遍历方式。通过阅读和理解这些代码，你可以更好地掌握二叉树遍历的原理和实践，这对于理解和解决涉及二叉树的算法问题...
在这个项目中，我们将深入探讨如何使用Java来实现一个迷宫的随机生成以及自动寻找路径的方法，同时会涉及树的深度遍历这一核心算法。 首先，迷宫生成通常采用的是深度优先搜索（DFS，Depth-First Search）或广度...
根据给定文件的信息，我们可以将相关的知识点归纳如下： ...通过以上介绍，我们可以看到图的遍历算法和最小生成树的实现是计算机科学中的重要组成部分，它们不仅应用于理论研究，也在实际工程中有着广泛的应用。
本篇将详细讲解如何使用Java实现图的深度优先遍历（DFS, Depth-First Search）和广度优先遍历（BFS, Breadth-First Search）。 1. **深度优先遍历（DFS）**： - DFS 是一种递归策略，它沿着某条路径深入到图的深处...
2. Ext JS 框架：这是一种富客户端开发框架，其 TreePanel 组件常用于实现树形视图，支持 TreeNode 和 AsyncTreeNode，后者用于动态加载树节点。 3. 动态生成树节点：两种策略，一次性生成所有节点和逐级加载，前者...
### 实现哈夫曼树的后序遍历 在数据结构的学习过程中，哈夫曼树是一种非常重要的非线性数据结构。它广泛应用于文件压缩、编码等领域。本篇文章将详细介绍如何构建一个哈夫曼树，并实现其后序遍历算法。 #### ...
有两种主要方式来初始化数组：直接初始化和动态初始化。直接初始化时，我们可以在声明时同时指定数组的大小和初始值，如： ```java int[] numbers = {1, 2, 3, 4, 5}; ``` 而动态初始化则是在声明时仅指定数组长度，...
在Java编程语言中，遍历数组是常见的操作，无论是在数据处理、算法实现还是其他程序设计中都必不可少。本文将详细介绍如何使用Java来遍历数组，并通过实例代码和注释帮助理解这一过程。 首先，Java中的数组是一种...
本篇文章将深入探讨二叉树的基本操作，包括初始化、遍历和求深度等核心概念。 **一、二叉树的初始化** 二叉树的初始化通常涉及创建一个空的二叉树或构建一个具有特定节点的二叉树。在编程语言中，可以使用类或...
决策树的Java实现涉及多个关键概念和技术点，包括但不限于节点的定义、数据结构的选择、属性的选择等。通过上述分析，我们不仅了解了决策树的基本原理，还深入了解了其在Java中的具体实现方式。这对于理解和开发实际...
1. 初始化和销毁树。 2. 创建树，根据给定的规则生成树结构。 3. 清除树，释放内存。 4. 判断树是否为空。 5. 获取树的深度。 6. 访问根节点、双亲节点、子节点。 7. 插入和删除子节点。 8. 遍历树，如前序、中序、...
在本文中，我们将深入探讨图的数据结构以及如何对图进行深度优先遍历（DFS）和广度优先遍历（BFS）。首先，我们要理解图的基本概念。图是一种数据结构，用于表示对象之间的关系，其中的对象称为顶点或节点，而它们...
本段代码展示了如何用C++实现树的深度优先遍历和广度优先遍历。虽然实际实现的是图的遍历，但原理和树的遍历非常相似，这里我们将其理解为树的遍历。 1. **数据结构定义**： - `const int MAX_VERTEX_NUM = 10;`：...
在VC++（Visual C++）开发环境中，实现树形目录遍历是一项常见的任务，尤其在文件管理系统或资源浏览器等应用中。本知识点将详细讲解如何使用递归算法来完成这一功能，以及涉及到的相关编程概念。 首先，理解目录...
"tree_反向层次遍历树_4321_"这个标题指的是一个特定的树遍历方法，即反向层次遍历（也称为反向深度优先搜索）。在标准的层次遍历（通常是从根节点开始，按照从上至下、从左至右的顺序访问节点）中，反向层次遍历则...