一,树
树是一种[数据结构]，它是由n（n>=0）个有限结点组成一个具有层次关系的[集合]。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
a，每个结点有零个或多个子结点；
b，没有父结点的结点称为根结点；
c，每一个非根结点有且只有一个父结点；
d，除了根结点外，每个子结点可以分为多个不相交的子树
那如何使用java来实现树的这种结构呢，我们可以以面向对象的思想来分析：
1，树根是谁
2，给定某个节点，则它的父节点是谁
3，给定某个节点，则它的子节点都有哪些
import java.util.ArrayList;
import java.util.List;
public class MyTree {
// 用于存储树种节点
private List<Node> list = new ArrayList<Node>();
// 节点内部类
class Node {
private String data;
private String father;
public Node(String data, String father) {
this.data = data;
this.father = father;
}
}
public void add(String father, String data) {
Node node = new Node(data, father);
list.add(node);
}
/**
* 根据子节点获取父节点
* @param children
* @return
*/
public String getFather(String children) {
for (int i=0; i<list.size(); i++) {
Node node = list.get(i);
if (node.data.equals(children)) {
return node.father;
}
}
return null;
}
/**
* 根据父节点获取所有子节点
* @param father
* @return
*/
public List<String> getChildren(String father) {
List<String> ret = new ArrayList<String>();
for (int i = 0; i < list.size(); i++) {
Node node = list.get(i);
if (node.father.equals(father)) {
ret.add(node.data);
}
}
return ret;
}
public static void main(String[] args) {
MyTree a = new MyTree();
a.add("世界", "亚洲");
a.add("世界", "美洲");
a.add("世界", "欧洲");
a.add("亚洲", "中国");
a.add("美洲", "美国");
a.add("亚洲", "日本");
a.add("中国", "河北");
a.add("中国", "河南");
a.add("中国", "广东");
a.add("中国", "浙江");
System.out.println(a.getFather("美国"));
System.out.println("---------------");
System.out.println(a.getChildren("中国"));
}
}
上面代码以内部类方式定义节点类， 然后实现了添加节点， 通过父节点找到所有子节点，通过子节点找到父节点等。这样就可以简单模拟一个逻辑意义上的树。
运行mian方法，简单测试该类
美洲
---------------
[河北, 河南, 广东, 浙江]
二，菜单简单实现
菜单是跟树有很多共同点，我们可以以树方式来处理菜单逻辑。
通过上边自己创建的tree，我们来做一个菜单。通过用户输入来获取菜单信息
代码如下：
package cn.tree.test;
import java.util.List;
import java.util.Scanner;
public class MyMenu {
MyTree tree = new MyTree();
public void add(String father, String data) {
tree.add(father, data);
}
public void run(String x) {
Scanner scan = new Scanner(System.in);
while (true) {
List<String> childrens = tree.getChildren(x);
if (childrens == null || childrens.isEmpty()) {
System.out.println("你选择了:"+x);
}
System.out.println("------------");
System.out.println("- " + x);
for (int i = 0; i < childrens.size(); i++) {
System.out.println(" " +i + "," + childrens.get(i));
}
System.out.println(" u,返回上一级");
System.out.println("------------");
System.out.println("请选择:");
String s = scan.nextLine();
if ("u".equals(s)) {
String x1 = tree.getFather(x);
if (x1 != null) {
x = x1;
continue;
} else {
System.out.println("已经到最顶层");
}
} else {
try {
x = childrens.get(Integer.valueOf(s));
} catch(Exception e) {
System.out.println("请重新选择:");
}
}
}
//run(childrens.get(Integer.valueOf(s)));递归也可以,循环也可以
}
public static void main(String[] args) {
MyMenu a = new MyMenu();
a.add("世界", "亚洲");
a.add("世界", "美洲");
a.add("世界", "欧洲");
a.add("亚洲", "中国");
a.add("美洲", "美国");
a.add("亚洲", "日本");
a.add("中国", "河北");
a.add("中国", "河南");
a.add("中国", "广东");
a.add("中国", "浙江");
a.run("世界");
}
}
运行结果如下：
------------
- 世界
0,亚洲
1,美洲
2,欧洲
u,返回上一级
------------
请选择:
1
------------
- 美洲
0,美国
u,返回上一级
------------
请选择:
u
------------
- 世界
0,亚洲
1,美洲
2,欧洲
u,返回上一级
------------
请选择:
0
------------
- 亚洲
0,中国
1,日本
u,返回上一级
------------
请选择:
0
------------
- 中国
0,河北
1,河南
2,广东
3,浙江
u,返回上一级
------------
请选择:
0
你选择了:河北
------------
- 河北
u,返回上一级
------------
请选择:
