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;
}
}
分享到：
相关推荐
- 尽管代码中没有直接实现查找特定节点的方法，但通过`getElders()`和`getJuniors()`方法，我们可以很容易地扩展实现对树的遍历和查找功能。例如，可以实现深度优先搜索（DFS）或广度优先搜索（BFS）算法来查找具有...
`DOM`解析器将整个XML文档加载到内存中，形成一个树形结构，便于遍历和操作；而`SAX`解析器则采用事件驱动的方式，逐个处理XML元素，对内存要求较低，适合处理大型XML文件。在这个项目中，由于树形菜单可能包含多层...
以上就是使用JavaScript实现多叉树的基本操作，包括创建、添加、遍历和移除节点。这些操作对于处理复杂的、层次分明的数据结构非常有用，提高了数据检索和管理的效率。在实际应用中，可以根据具体需求定制遍历策略和...
- 扩展知识，如多叉树的层次遍历等。 这个资源可能还会涉及到如何通过图形化工具（如Graphviz）绘制二叉树，以便更好地理解和展示层序遍历的过程。 总之，二叉树层序遍历是一个重要的数据结构和算法主题，对于理解...
在Java和JavaScript中，无限层级的树形结构是...总的来说，无论是Java还是JavaScript，实现无限层级的树形结构都涉及到数据的分组、遍历和递归操作。理解这些基本概念，可以帮助开发者有效地处理复杂的数据层次结构。
在多叉树或其他类型的树结构中，头结点的概念仍然适用，只是节点可以有多个子节点。 **代码实现** 在给定的文件`main.java`中，很可能是实现了寻找链表或树头结点的代码。`README.txt`文件可能包含了关于该代码的...
然而，在某些情况下，我们需要处理具有超过两个子节点的树（即多路树或多叉树）。本篇将详细介绍几种实现这类树的方法。 #### 1. 多子节点树的实现方法 ##### 1.1 数组表示法 (Array of Children) 一种直观的方法...
- **树形结构**: 数据元素之间存在一对多的关系，如二叉树、多叉树等。 - **图形结构**: 数据元素之间存在多对多的关系，如图结构中的顶点通过边相互连接。 **4. 设有数据的逻辑结构的二元组定义形式为B=(D,R)，...