java模拟树形结构
/**
* 自定义树形结构
* 可以通过任意结点找到1.当前结点的子结点2.当前结点的父结点3.当前结点的兄弟结点4.当前结点的祖先结点5.当前结点的子孙结点
*/
public class CustomizeTree<K> {
private HashMap<K,K> childToParent;
//用map<K child,V parent> 记录每一个子结点向父结点的映射关系 树形结构中每一个结点只有一个父结点，所以V也是单一结点
private HashMap<K, LinkedList<K>> parentToChildren;
//map<K parent,V children> 记录每个父结点向子结点们的映射关系 树形结构中结点不限制子结点的个数 因为K唯一，用一个K对应多个子结点需要使用集合存放多个子结点来表示V
public CustomizeTree() {
childToParent = new HashMap<>();
parentToChildren = new HashMap<>();
}
public void put(K parent, K child){
//每次添加只添加一对一映射关系
K oldPar = childToParent.put(child,parent);
if (oldPar!=null){
//如果发生了父结点的替换，则将child从原父结点的子结点集合中移除
parentToChildren.get(oldPar).remove(child);
}
if (!parentToChildren.containsKey(parent)){
//判断该父结点-子结点集合的映射是否已存在，存在则增加子结点集合的内容，不存在则新建映射
parentToChildren.put(parent,new LinkedList<>());
}
parentToChildren.get(parent).add(child);
//通过key调用value链表添加子结点
}
public LinkedList<K> getChildren(K parent){
return parentToChildren.get(parent);
}
public K getParent(K child){
return childToParent.get(child);
}
public LinkedList<K> getBrothers(K node){
K parent = childToParent.get(node);
LinkedList<K> children = new LinkedList<>(parentToChildren.get(parent));
//将父结点的子结点集合传参给构造器，生成一个副本，如果直接调用原value进行删除当前结点并返回操作会造成原始数据的改变，get只是查看并不应该进行修改
children.remove(node);
return children;
}
public LinkedList<K> getForefathers(K child){
//返回祖先结点集合
LinkedList<K> forefathers = new LinkedList<>();
for (K node = childToParent.get(child);node != null;node = childToParent.get(node)){
forefathers.add(node);
}
return forefathers;
}
public LinkedList<K> getDescendants(K parent){
//返回子孙结点集合
LinkedList<K> list = new LinkedList<>();
getAllChildren(list,parent);
return list;
//这里同样不能使用parentToChildren.get(K).addAll来添加结点，这会改变原始数据
}
private void getAllChildren(LinkedList<K> list,K parent){
LinkedList<K> children = parentToChildren.get(parent);
if (children!=null) {
//当map中没有K parent时.get()返回null
list.addAll(children);
for (K child :
children) {
getAllChildren(list, child);
//递归，将每个子结点集合添加到list中
}
}
}
}
class biology1{
//创建生物类树形图测试树形结构
public static void main(String[] args) {
CustomizeTree<String> bio = new CustomizeTree<>();
bio.put("有机物","生物");
bio.put("生物","动物");
bio.put("生物","植物");
bio.put("生物","微生物");
bio.put("动物","脊椎动物");
bio.put("动物","脊索动物");
bio.put("动物","腔肠动物");
bio.put("脊椎动物","哺乳类");
bio.put("脊椎动物","爬行类");
bio.put("哺乳类","人类");
bio.put("哺乳类","猫科动物");
bio.put("哺乳类","牛");
System.out.println(bio.getParent("生物"));
System.out.println(bio.getChildren("腔肠动物"));
System.out.println(bio.getChildren("脊椎动物"));
System.out.println(bio.getBrothers("猫科动物"));
System.out.println(bio.getForefathers("爬行类"));
System.out.println(bio.getDescendants("动物"));
}
}
class Tree2<E>{
//使用树结点来模拟树形结构
private static final class Node<E>{
E item;
Node<E> parent;
LinkedList<Node<E>> children;
//不限制子结点的数量
public Node(E item, Node<E> parent, LinkedList<Node<E>> children) {
this.item = item;
this.parent = parent;
this.children = children;
}
}
Node<E> root;
public boolean add(E parentE,E...childrenE){
//形参第一个为父结点，后面的用可变参数接收，都为子结点
if (parentE==null)return false;
Node<E> p;
if (root==null){
root = new Node<>(parentE,null,new LinkedList<>());
if (childrenE==null)return true;
//如果没有写子结点直接创建根结点后返回
p = root;
}else if ((p=getNode(parentE))==null||childrenE==null||containsSomeOf(childrenE)){
//容器中有结点的情况下，不存在存储parent的结点 或者 没有写子结点 或者 已存在存储了children中某些元素的结点时添加失败
return false;
}
//变量p无论走if还是elif的情况都被赋值为父结点
for (E childE :
childrenE) {
p.children.add(new Node<>(childE,p,new LinkedList<>()));
//叶子结点的children.size()=0
}
return true;
}
private Node<E> getNode(E e){
if (root==null||e==null)return null;
return getNode(root,e);
}
private Node<E> getNode(Node<E> n,E e){
if (e.equals(n.item)){
return n;
}
if (!n.children.isEmpty()){
//子结点集合不空时对每一个子结点递归
Node<E> p;
for (Node<E> child :
n.children) {
p = getNode(child, e);
if (p!= null){
return p;
//当找到结点时会将p层层返回
}
}
}
return null;
}
private boolean containsSomeOf(E...childrenE){
for (E childE :
childrenE) {
if (getNode(childE) != null){
return true;
}
}
return false;
}
public Object[] getChildren(E e){
Node<E> n = getNode(e);
return n==null?null:toArrayList(n.children).toArray();
//当找不到e时返回null，当存储e的结点没有子结点时返回[]，否则返回子结点.item数组，这样区分了不存在e和存在e但没有子结点的情况
//n.children为LinkedList<Node<E>>类型，直接.toArray()为Node<E>数组，所以需要先将.item取出再组成数组返回
}
private ArrayList<E> toArrayList(LinkedList<Node<E>> nodes){
//返回类型的泛型为E，不是Node<E>
if (nodes.isEmpty())return new ArrayList<>();
ArrayList<E> arr = new ArrayList<>(nodes.size());
//将arr的size初始化为nodes的size
for (Node<E> n :
nodes) {
arr.add(n.item);
}
return arr;
}
public E getParent(E e){
Node<E> n = getNode(e);
return (n==null||n==root)?null:n.parent.item;
}
public Object[] getBrothers(E e){
Node<E> n = getNode(e);
if (n==null)return null;
if (n==root)return new Object[]{};
//根结点没有兄弟结点
ArrayList<E> arr = toArrayList(n.parent.children);
arr.remove(e);
return arr.toArray();
}
public Object[] getForefathers(E e){
Node<E> n = getNode(e);
if (n==null)return null;
ArrayList<E> arr = new ArrayList<>();
for (n = n.parent;n!=null;n = n.parent){
//当n在第一次循环之前为根结点时不执行循环
arr.add(n.item);
}
return arr.toArray();
}
public Object[] getDescendants(E e){
Node<E> n = getNode(e);
return n==null?null:
toArrayList(getAllChildren(new LinkedList<>(),n)).toArray();
//传一个新的容器用于存放子结点，getAll返回结点集合，toArrayList返回元素集合
}
private LinkedList<Node<E>> getAllChildren(LinkedList<Node<E>> list,Node<E> n){
LinkedList<Node<E>> children = n.children;
if (children.isEmpty())return children;
list.addAll(children);
for (Node<E> child :
children) {
getAllChildren(list, child);
}
return list;
}
}
class biology2{
public static void main(String[] args) {
Tree2<String> tree2 = new Tree2<>();
//测试略
}
}
