多叉树的复习
多叉树复习
「多叉树」就是分 N 岔的树，每個节点可以有零个、一个、两个、……、 N 个小孩。 类似：
本文主要内容为: 1. 文件读入树状数据（json格式），构造多叉树 2. 多叉树的深度遍历 3. 多叉树的层次遍历
多叉树节点构造
public class TreePieNode {
private String name;//节点名字
private ArrayList<TreePieNode> children = null;//子节点
private TreePieNode parent = null;//父节点
private int level;//深度
public TreePieNode(String name, ArrayList<TreePieNode> children,
TreePieNode parent, int level) {
super();
this.name = name;
this.children = children;
this.parent = parent;
this.level = level;
}
public TreePieNode() {
super();
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public ArrayList<TreePieNode> getChildren() {
return children;
}
public void setChildren(ArrayList<TreePieNode> children) {
this.children = children;
}
public TreePieNode getParent() {
return parent;
}
public void setParent(TreePieNode parent) {
this.parent = parent;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
}
读取文件生成树
/**
* read data from the json file
*
* @param pathName
* the path of json file
* @return the whole data of the tree
*/
public String fileInput(String pathName) {
File file = new File(pathName);
String context = null;
FileReader fileReader = null;
BufferedReader bufferedReader = null;
try {
fileReader = new FileReader(file);
bufferedReader = new BufferedReader(fileReader);
String temp = null;
StringBuffer stringBuffer = new StringBuffer();
while ((temp = bufferedReader.readLine()) != null)
stringBuffer.append(temp);
context = stringBuffer.toString();
} catch (IOException e) {
} finally {
try {
bufferedReader.close();
fileReader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
return context;
}
String context = fileInput(pathname);
TreePieNode rootNode = JSON.parseObject(context, TreePieNode.class);
深度遍历
/**
* @param node the rootNode of the tree
*/
public void depthFirstTraverse(TreePieNode node) {
ArrayList<TreePieNode> nodeList = node.getChildren();
float size = 0f;
if (nodeList != null) {
for (TreePieNode tmpNode : node.getChildren()) {
process(tmpNode);
System.out.println(tmpNode.getName());
}
}
}
层次遍历
/**
* @param root
* @retrun a stack of all tree nodes
*/
public Stack iteratorTree(TreePieNode root) {
TreePieNode p = null;
Queue<TreePieNode> q = null;
Stack<TreePieNode> s = null;
q = new LinkedList<TreePieNode>();
s = new Stack();
root.setLevel(0);
q.offer(root);
while (q.isEmpty() == false) {
p = q.poll();
if (p.getChildren() != null) {
for (int i = 0; i < p.getChildren().size(); i++) {
TreePieNode tmpNode = p.getChildren().get(i);
tmpNode.setLevel(p.getLevel() + 1);
q.offer(p.getChildren().get(i));
}
}
s.push(p);
}
return s;
}
测试代码和结果
System.out.println("深度优先");
process(rootNode);
System.out.println("广度优先");
s = f1(rootNode);
TreePieNode p = null;
while(s.isEmpty()== false){
p = s.pop();
System.out.println(p.getName()+" :"+p.getLevel());
}
//深度优先
//Hight
//width
//AgglomerativeCluster
//CommunityStructure
//HierarchicalCluster
//MergeEdge
//cluster
//BetweennessCentrality
//LinkDistance
//MaxFlowMinCut
//ShortestPaths
//SpanningTree
//graph
//analytics
//Easing
//FunctionSequence
//ArrayInterpolator
//ColorInterpolator
//DateInterpolator
//Interpolator
//MatrixInterpolator
//NumberInterpolator
//ObjectInterpolator
//PointInterpolator
//RectangleInterpolator
//interpolate
//ISchedulable
//Parallel
//Pause
//Scheduler
//Sequence
//Transition
//Transitioner
//TransitionEvent
//Tween
//animate
//广度优先
//width :4
//Hight :4
//RectangleInterpolator :3
//PointInterpolator :3
//ObjectInterpolator :3
//NumberInterpolator :3
//MatrixInterpolator :3
//Interpolator :3
//DateInterpolator :3
//ColorInterpolator :3
//ArrayInterpolator :3
//SpanningTree :3
//ShortestPaths :3
//MaxFlowMinCut :3
//LinkDistance :3
//BetweennessCentrality :3
//MergeEdge :3
//HierarchicalCluster :3
//CommunityStructure :3
//AgglomerativeCluster :3
//Tween :2
//TransitionEvent :2
//Transitioner :2
//Transition :2
//Sequence :2
//Scheduler :2
//Pause :2
//Parallel :2
//ISchedulable :2
//interpolate :2
//FunctionSequence :2
//Easing :2
//graph :2
//cluster :2
//animate :1
//analytics :1
//flare :0
blog comments powered by Disqus