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 数组初始化 详解 doc
本文实例讲述了Python实现的多叉树寻找最短路径算法。分享给大家供大家参考,具体如下: 多叉树的最短路径: 思想: 传入start 和 end 两个 目标值 1 找到从根节点到目标节点的路径 2 从所在路径,寻找最近的...
利用MySQL存储过程实现树的初始化、插入、深度遍历、按层遍历、删除操作。可以作为学习存储过程的笑demo
Java实验-数组的定义、初始化方法 掌握数组的遍历方法 掌握Arryas类的使用
resetnode:初始化所有节点,把所有节点初始化成根节点下的子节点 restore:恢复节点:@ID,把删除的节点恢复到哪个节点下,@Name(节点ID):恢复哪个节点 ---------------------------------------- MPTT_NODEMove ...
NULL 博文链接:https://yuu1987.iteye.com/blog/1113142
52.java二维数组静态初始化.zip52.java二维数组静态初始化.zip52.java二维数组静态初始化.zip52.java二维数组静态初始化.zip52.java二维数组静态初始化.zip52.java二维数组静态初始化.zip52.java二维数组静态初始化....
51.java二维数组动态初始化.zip51.java二维数组动态初始化.zip51.java二维数组动态初始化.zip51.java二维数组动态初始化.zip51.java二维数组动态初始化.zip51.java二维数组动态初始化.zip51.java二维数组动态初始化....
SpringBoot项目启动时实现调用一次初始化方法
45.java数组动态初始化.zip45.java数组动态初始化.zip45.java数组动态初始化.zip45.java数组动态初始化.zip45.java数组动态初始化.zip45.java数组动态初始化.zip45.java数组动态初始化.zip45.java数组动态初始化.zip...
44.java数组静态初始化.zip44.java数组静态初始化.zip44.java数组静态初始化.zip44.java数组静态初始化.zip44.java数组静态初始化.zip44.java数组静态初始化.zip44.java数组静态初始化.zip44.java数组静态初始化.zip...
主要介绍了6种方法初始化JAVA中的list集合,文中讲解非常详细,代码帮助大家更好的理解和学习,感兴趣的朋友可以了解下
详细介绍了Java的静态成员变量、静态数据块、非静态成员变量和非静态成员变量等初始化顺序
邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历 邻接矩阵表示法深度遍历和广度遍历
java语法\Java数组声明、创建、初始化
介绍java对象的创建、初始化、和引用。并分析一下JAVA中对象创建和初始化过程中涉及的相关概念问题。
介绍一下java程序初始化的顺序,这会对您以后的开发所有帮助
一个java代码初始化具体过程的的demo
java编程思想-初始化与清理了解this之后,你就能更全面地理解“静态(static)方法”的含义。静态方法就是没有this的方法。在“静态方法”的内部不能调用“非静态方法”,反过来倒是可以的。而且你可以在没有创建...