方法一:
1. 带有父节点信息的节点:
public class FlatNode {
private Integer path;
private String name;
private Integer parent;
public Integer getPath() {
return path;
}
public void setPath(Integer path) {
this.path = path;
}
public Integer getParent() {
return parent;
}
public void setParent(Integer parent) {
this.parent = parent;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "FlatNode{" +
"path=" + path +
", name='" + name + '\'' +
", parent=" + parent +
'}';
}
}
2. 多叉树的节点:
public class MulNode {
private Integer path;
private String name;
private List<MulNode> childList;
public Integer getPath() {
return path;
}
public void setPath(Integer path) {
this.path = path;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public List<MulNode> getChildList() {
return childList;
}
public void setChildList(List<MulNode> childList) {
this.childList = childList;
}
public boolean hasChildren(MulNode node) {
return node.getChildList() != null && node.getChildList().size() > 0;
}
@Override
public String toString() {
return "MulNode{" +
"path=" + path +
", name='" + name + '\'' +
", childList=" + childList +
'}';
}
}
3.工具类,包括多叉树遍历查找节点方法(利用队列进行递归层序遍历 PS :从二叉树层序遍历得到的灵感)
二叉树转换成带有父节点信息的一位数组方法(同样是利用递归)
测试方法--main函数。
public class NodeUtils {
public static MulNode find(MulNode root, Integer value) {
Queue<MulNode> queue = new LinkedList<MulNode>();
queue.add(root);
return find(queue, value);
}
// 层序遍历
private static MulNode find(Queue<MulNode> queue, Integer value) {
MulNode res = null;
while (!queue.isEmpty()) {
MulNode node = queue.peek();
if (node.getPath().equals(value)) {
res = node;
break;
} else {
queue.remove();
if (node.hasChildren(node)) {
for (MulNode child : node.getChildList()) {
queue.add(child);
}
} else {
find(queue, value);
}
}
}
return res;
}
public static List<FlatNode> transfer(MulNode root) {
Queue<MulNode> queue = new LinkedList<MulNode>();
queue.add(root);
Queue<MulNode> parent = new LinkedList<MulNode>();
List<FlatNode> nodeList = new ArrayList<FlatNode>();
return transfer(queue, parent, nodeList);
}
private static List<FlatNode> transfer(Queue<MulNode> queue, Queue<MulNode> parent, List<FlatNode> nodeList) {
while (!queue.isEmpty()) {
MulNode node = queue.peek();
MulNode father = parent.peek();
FlatNode flatNode = new FlatNode();
flatNode.setName(node.getName());
flatNode.setPath(node.getPath());
if (father == null) {
flatNode.setParent(null);
} else {
flatNode.setParent(father.getPath());
parent.remove();
}
queue.remove();
nodeList.add(flatNode);
if (node.hasChildren(node)) {
for (MulNode child : node.getChildList()) {
queue.add(child);
parent.add(node);
}
} else {
transfer(queue, parent, nodeList);
}
}
return nodeList;
}
public static void main(String[] args) {
MulNode root = new MulNode();
root.setPath(0);
root.setName("root");
MulNode node1 = new MulNode();
node1.setPath(1);
node1.setName("Clothes");
MulNode node2 = new MulNode();
node2.setPath(2);
node2.setName("food");
MulNode node3 = new MulNode();
node3.setPath(3);
node3.setName("Animal");
MulNode node10 = new MulNode();
node10.setPath(10);
node10.setName("shoe");
MulNode node11 = new MulNode();
node11.setPath(11);
node11.setName("skirt");
MulNode node12 = new MulNode();
node12.setPath(12);
node12.setName("jacket");
MulNode node20 = new MulNode();
node20.setPath(20);
node20.setName("pizza");
MulNode node21 = new MulNode();
node21.setPath(21);
node21.setName("noodle");
MulNode node30 = new MulNode();
node30.setPath(30);
node30.setName("hen");
MulNode node31 = new MulNode();
node31.setPath(31);
node31.setName("pig");
MulNode node32 = new MulNode();
node32.setPath(32);
node32.setName("wolf");
MulNode node200 = new MulNode();
node200.setPath(200);
node200.setName("Italy Pizza");
List<MulNode> list1 = new ArrayList<MulNode>();
List<MulNode> list10 = new ArrayList<MulNode>();
List<MulNode> list20 = new ArrayList<MulNode>();
List<MulNode> list30 = new ArrayList<MulNode>();
List<MulNode> list200 = new ArrayList<MulNode>();
list200.add(node200);
node20.setChildList(list200);
list20.add(node20);
list20.add(node21);
node2.setChildList(list20);
list30.add(node30);
list30.add(node31);
list30.add(node32);
node3.setChildList(list30);
list10.add(node10);
list10.add(node11);
list10.add(node12);
node1.setChildList(list10);
list1.add(node1);
list1.add(node2);
list1.add(node3);
root.setChildList(list1);
System.out.println(root);
System.out.println(find(root, 32));
System.out.print(transfer(root));
}
}
方法二:利用map来构造树形结构:
public class MulNode {
private int id;
private int parentId;
MulNode parent;
List<MulNode> childList;
String code;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getParentId() {
return parentId;
}
public void setParentId(int parentId) {
this.parentId = parentId;
}
public MulNode getParent() {
return parent;
}
public void setParent(MulNode parent) {
this.parent = parent;
}
public List<MulNode> getChildList() {
return childList;
}
public void setChildList(List<MulNode> childList) {
this.childList = childList;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public MulNode(int id, int parentId, MulNode parent, List<MulNode> childList, String code) {
this.id = id;
this.parentId = parentId;
this.parent = parent;
this.childList = childList;
this.code = code;
}
//根据List构造树形结构
public Map<Integer, MulNode> generateTree(List<MulNode> nodeList) {
Map<Integer, MulNode> treeMap = new HashMap<Integer, MulNode>();
for (MulNode node : nodeList) {
treeMap.put(node.getId(), node);
}
for (MulNode value : treeMap.values()) {
MulNode parent = treeMap.get(value.getParentId());
if (parent != null) {
parent.getChildList().add(value);
value.setParent(parent);
}
}
return treeMap;
}
//构造path结构
public Map<String, MulNode> generateTreePath(Map<Integer, MulNode> treeMap) {
Map<String, MulNode> pathMap = new HashMap<String, MulNode>();
for (MulNode value : treeMap.values()) {
pathMap.put(generateTreePath(value), value);
}
return pathMap;
}
/**
* 生成 具体配置 Path
*
* @param node
* @return
*/
public String generateTreePath(MulNode node) {
if (null == node.getParent()) {
return node.getCode();
} else {
return generateTreePath(node.getParent()) + "/" + node.getCode();
}
}
}
相关推荐
java多叉树的实现:节点集合生成多叉树,单个节点添加到多叉树,深度遍历,广度遍历
新概念智能树形菜单--利用加权多叉树结合
本主要是树状数据(多叉树)在数据库中存储的示例源码,同时包含数据表的设计示例,满满的代码干货
多叉树的构建,包含测试代码
1 package tree; 2 3 import java.util.List; 4 import java.util.ArrayList; 5 import java.io.Serializable; 6 7 public class TreeNode implements Serializable { 8 private int parentId...
C#实现多叉树的后序遍历。高效地实现后序遍历多叉树。
多叉树的遍历,可以打印出树形结构,也可以只打印叶节点,或打印指定层的节点(一位德国教授写的文章)可以按照文章中给的网址下载源代码,
三叉树多叉树遍历 c# 2.0
多叉树的实现,本算法采用5比较合适,纵向遍历靠递归调用
现了一个多叉树建立函数,建立函数根据用户的输入,首先建立一个新的节点,然后根据B的值进行深度递归调用。用户输入节点的顺序就是按照深度递归的顺序。另外,我们实现了一个层次优先遍历函数。该函数用一个队列...
分层建立一个随机层数及子节点的多叉树,并分层遍历输出,在都是奇数节点位置插入偶数节点,输出格式为树状
决策树 id3算法实现多叉树树形图显示,使用matlab编程实现多叉树生成结构体,再对结构体进行处理,生成树形图。
使用C++模板实现了,基于顺序存储的泛型多叉树容器, 其中包括前序、后序、兄弟、叶子、深度5种迭代器的实现,方便了多叉树的遍历。
说明地址 http://www.cnblogs.com/l2017/p/8660089.html
基于Python的多叉树遍历算法
利用多叉树解析关键字,另外还包括自制滑动引擎的实现。
动态生成多叉树,实现多叉树的自动化遍历,能生成XML文本。 指定子节点和父节点自动生成多叉树!
一个老外用C++编写的多叉树结构代码,代码简单,可以仅适用tree.h文件(需包含stack、vector等头文件)。示范工程为vs2005。
本程序主要介绍使用c语言的树数据结构,比较全面的介绍和使用多叉树。
多叉树的建立以及后序非递归遍历,希望对学习数据结构的同学有所帮助,也对树一部分有更深的了解。