/**

* 自定义树形结构

* 可以通过任意结点找到1.当前结点的子结点2.当前结点的父结点3.当前结点的兄弟结点4.当前结点的祖先结点5.当前结点的子孙结点

*/

public class CustomizeTree {

private HashMap childToParent;

//用map 记录每一个子结点向父结点的映射关系 树形结构中每一个结点只有一个父结点，所以V也是单一结点

private HashMap> parentToChildren;

//map 记录每个父结点向子结点们的映射关系 树形结构中结点不限制子结点的个数 因为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 getChildren(K parent){

return parentToChildren.get(parent);

}

public K getParent(K child){

return childToParent.get(child);

}

public LinkedList getBrothers(K node){

K parent = childToParent.get(node);

LinkedList children = new LinkedList<>(parentToChildren.get(parent));

//将父结点的子结点集合传参给构造器，生成一个副本，如果直接调用原value进行删除当前结点并返回操作会造成原始数据的改变，get只是查看并不应该进行修改

children.remove(node);

return children;

}

public LinkedList getForefathers(K child){

//返回祖先结点集合

LinkedList forefathers = new LinkedList<>();

for (K node = childToParent.get(child);node != null;node = childToParent.get(node)){

forefathers.add(node);

}

return forefathers;

}

public LinkedList getDescendants(K parent){

//返回子孙结点集合

LinkedList list = new LinkedList<>();

getAllChildren(list,parent);

return list;

//这里同样不能使用parentToChildren.get(K).addAll来添加结点，这会改变原始数据

}

private void getAllChildren(LinkedList list,K parent){

LinkedList 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 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{

//使用树结点来模拟树形结构

private static final class Node{

E item;

Node parent;

LinkedList> children;

//不限制子结点的数量

public Node(E item, Node parent, LinkedList> children) {

this.item = item;

this.parent = parent;

this.children = children;

}

}

Node root;

public boolean add(E parentE,E...childrenE){

//形参第一个为父结点，后面的用可变参数接收，都为子结点

if (parentE==null)return false;

Node 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 getNode(E e){

if (root==null||e==null)return null;

return getNode(root,e);

}

private Node getNode(Node n,E e){

if (e.equals(n.item)){

return n;

}

if (!n.children.isEmpty()){

//子结点集合不空时对每一个子结点递归

Node p;

for (Node 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 n = getNode(e);

return n==null?null:toArrayList(n.children).toArray();

//当找不到e时返回null，当存储e的结点没有子结点时返回[]，否则返回子结点.item数组，这样区分了不存在e和存在e但没有子结点的情况

//n.children为LinkedList>类型，直接.toArray()为Node数组，所以需要先将.item取出再组成数组返回

}

private ArrayList toArrayList(LinkedList> nodes){

//返回类型的泛型为E，不是Node

if (nodes.isEmpty())return new ArrayList<>();

ArrayList arr = new ArrayList<>(nodes.size());

//将arr的size初始化为nodes的size

for (Node n :

nodes) {

arr.add(n.item);

}

return arr;

}

public E getParent(E e){

Node n = getNode(e);

return (n==null||n==root)?null:n.parent.item;

}

public Object[] getBrothers(E e){

Node n = getNode(e);

if (n==null)return null;

if (n==root)return new Object[]{};

//根结点没有兄弟结点

ArrayList arr = toArrayList(n.parent.children);

arr.remove(e);

return arr.toArray();

}

public Object[] getForefathers(E e){

Node n = getNode(e);

if (n==null)return null;

ArrayList 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 n = getNode(e);

return n==null?null:

toArrayList(getAllChildren(new LinkedList<>(),n)).toArray();

//传一个新的容器用于存放子结点，getAll返回结点集合，toArrayList返回元素集合

}

private LinkedList> getAllChildren(LinkedList> list,Node n){

LinkedList> children = n.children;

if (children.isEmpty())return children;

list.addAll(children);

for (Node child :

children) {

getAllChildren(list, child);

}

return list;

}

}

class biology2{

public static void main(String[] args) {

Tree2 tree2 = new Tree2<>();

//测试略

}

}