/**
* 自定義樹形結(jié)構(gòu)
* 可以通過任意結(jié)點(diǎn)找到1.當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)2.當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)3.當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)4.當(dāng)前結(jié)點(diǎn)的祖先結(jié)點(diǎn)5.當(dāng)前結(jié)點(diǎn)的子孫結(jié)點(diǎn)
*/
public class CustomizeTree<K> {
? ?private HashMap<K,K> childToParent;
? ?//用map<K child,V parent> 記錄每一個(gè)子結(jié)點(diǎn)向父結(jié)點(diǎn)的映射關(guān)系 樹形結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)，所以V也是單一結(jié)點(diǎn)
? ?private HashMap<K, LinkedList<K>> parentToChildren;
? ?//map<K parent,V children> 記錄每個(gè)父結(jié)點(diǎn)向子結(jié)點(diǎn)們的映射關(guān)系 樹形結(jié)構(gòu)中結(jié)點(diǎn)不限制子結(jié)點(diǎn)的個(gè)數(shù) 因?yàn)镵唯一，用一個(gè)K對(duì)應(yīng)多個(gè)子結(jié)點(diǎn)需要使用集合存放多個(gè)子結(jié)點(diǎn)來表示V
? ?public CustomizeTree() {
? ? ? ?childToParent = new HashMap<>();
? ? ? ?parentToChildren = new HashMap<>();
? ?}

? ?public void put(K parent, K child){
? ? ? ?//每次添加只添加一對(duì)一映射關(guān)系
? ? ? ?K oldPar = childToParent.put(child,parent);
? ? ? ?if (oldPar!=null){
? ? ? ? ? ?//如果發(fā)生了父結(jié)點(diǎn)的替換，則將child從原父結(jié)點(diǎn)的子結(jié)點(diǎn)集合中移除
? ? ? ? ? ?parentToChildren.get(oldPar).remove(child);
? ? ? ?}
? ? ? ?if (!parentToChildren.containsKey(parent)){
? ? ? ? ? ?//判斷該父結(jié)點(diǎn)-子結(jié)點(diǎn)集合的映射是否已存在，存在則增加子結(jié)點(diǎn)集合的內(nèi)容，不存在則新建映射
? ? ? ? ? ?parentToChildren.put(parent,new LinkedList<>());
? ? ? ?}
? ? ? ?parentToChildren.get(parent).add(child);
? ? ? ?//通過key調(diào)用value鏈表添加子結(jié)點(diǎn)
? ?}

? ?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));
? ? ? ?//將父結(jié)點(diǎn)的子結(jié)點(diǎn)集合傳參給構(gòu)造器，生成一個(gè)副本，如果直接調(diào)用原value進(jìn)行刪除當(dāng)前結(jié)點(diǎn)并返回操作會(huì)造成原始數(shù)據(jù)的改變，get只是查看并不應(yīng)該進(jìn)行修改
? ? ? ?children.remove(node);
? ? ? ?return children;
? ?}

? ?public LinkedList<K> getForefathers(K child){
? ? ? ?//返回祖先結(jié)點(diǎn)集合
? ? ? ?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){
? ? ? ?//返回子孫結(jié)點(diǎn)集合
? ? ? ?LinkedList<K> list = new LinkedList<>();
? ? ? ?getAllChildren(list,parent);
? ? ? ?return list;
? ? ? ?//這里同樣不能使用parentToChildren.get(K).addAll來添加結(jié)點(diǎn)，這會(huì)改變?cè)紨?shù)據(jù)
? ?}
? ?private void getAllChildren(LinkedList<K> list,K parent){
? ? ? ?LinkedList<K> children = parentToChildren.get(parent);
? ? ? ?if (children!=null) {
? ? ? ? ? ?//當(dāng)map中沒有K parent時(shí).get()返回null
? ? ? ? ? ?list.addAll(children);
? ? ? ? ? ?for (K child :
? ? ? ? ? ? ? ? ? ?children) {
? ? ? ? ? ? ? ?getAllChildren(list, child);
? ? ? ? ? ? ? ?//遞歸，將每個(gè)子結(jié)點(diǎn)集合添加到list中
? ? ? ? ? ?}
? ? ? ?}
? ?}

}
class biology1{
? ?//創(chuàng)建生物類樹形圖測(cè)試樹形結(jié)構(gòu)
? ?public static void main(String[] args) {
? ? ? ?CustomizeTree<String> bio = new CustomizeTree<>();
? ? ? ?bio.put("有機(jī)物","生物");
? ? ? ?bio.put("生物","動(dòng)物");
? ? ? ?bio.put("生物","植物");
? ? ? ?bio.put("生物","微生物");
? ? ? ?bio.put("動(dòng)物","脊椎動(dòng)物");
? ? ? ?bio.put("動(dòng)物","脊索動(dòng)物");
? ? ? ?bio.put("動(dòng)物","腔腸動(dòng)物");
? ? ? ?bio.put("脊椎動(dòng)物","哺乳類");
? ? ? ?bio.put("脊椎動(dòng)物","爬行類");
? ? ? ?bio.put("哺乳類","人類");
? ? ? ?bio.put("哺乳類","貓科動(dòng)物");
? ? ? ?bio.put("哺乳類","牛");
? ? ? ?System.out.println(bio.getParent("生物"));
? ? ? ?System.out.println(bio.getChildren("腔腸動(dòng)物"));
? ? ? ?System.out.println(bio.getChildren("脊椎動(dòng)物"));
? ? ? ?System.out.println(bio.getBrothers("貓科動(dòng)物"));
? ? ? ?System.out.println(bio.getForefathers("爬行類"));
? ? ? ?System.out.println(bio.getDescendants("動(dòng)物"));
? ?}
}

class Tree2<E>{
? ?//使用樹結(jié)點(diǎn)來模擬樹形結(jié)構(gòu)
? ?private static final class Node<E>{
? ? ? ?E item;
? ? ? ?Node<E> parent;
? ? ? ?LinkedList<Node<E>> children;
? ? ? ?//不限制子結(jié)點(diǎn)的數(shù)量

? ? ? ?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){
? ? ? ?//形參第一個(gè)為父結(jié)點(diǎn)，后面的用可變參數(shù)接收，都為子結(jié)點(diǎn)
? ? ? ?if (parentE==null)return false;
? ? ? ?Node<E> p;
? ? ? ?if (root==null){
? ? ? ? ? ?root = new Node<>(parentE,null,new LinkedList<>());
? ? ? ? ? ?if (childrenE==null)return true;
? ? ? ? ? ?//如果沒有寫子結(jié)點(diǎn)直接創(chuàng)建根結(jié)點(diǎn)后返回
? ? ? ? ? ?p = root;
? ? ? ?}else if ((p=getNode(parentE))==null||childrenE==null||containsSomeOf(childrenE)){
? ? ? ? ? ?//容器中有結(jié)點(diǎn)的情況下，不存在存儲(chǔ)parent的結(jié)點(diǎn) 或者 沒有寫子結(jié)點(diǎn) 或者 已存在存儲(chǔ)了children中某些元素的結(jié)點(diǎn)時(shí)添加失敗
? ? ? ? ? ?return false;
? ? ? ?}
? ? ? ?//變量p無論走if還是elif的情況都被賦值為父結(jié)點(diǎn)
? ? ? ?for (E childE :
? ? ? ? ? ? ? ?childrenE) {
? ? ? ? ? ?p.children.add(new Node<>(childE,p,new LinkedList<>()));
? ? ? ? ? ?//葉子結(jié)點(diǎn)的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()){
? ? ? ? ? ?//子結(jié)點(diǎn)集合不空時(shí)對(duì)每一個(gè)子結(jié)點(diǎn)遞歸
? ? ? ? ? ?Node<E> p;
? ? ? ? ? ?for (Node<E> child :
? ? ? ? ? ? ? ? ? ?n.children) {
? ? ? ? ? ? ? ?p = getNode(child, e);
? ? ? ? ? ? ? ?if (p!= null){
? ? ? ? ? ? ? ? ? ?return p;
? ? ? ? ? ? ? ? ? ?//當(dāng)找到結(jié)點(diǎn)時(shí)會(huì)將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();
? ? ? ?//當(dāng)找不到e時(shí)返回null，當(dāng)存儲(chǔ)e的結(jié)點(diǎn)沒有子結(jié)點(diǎn)時(shí)返回[]，否則返回子結(jié)點(diǎn).item數(shù)組，這樣區(qū)分了不存在e和存在e但沒有子結(jié)點(diǎn)的情況
? ? ? ?//n.children為L(zhǎng)inkedList<Node<E>>類型，直接.toArray()為Node<E>數(shù)組，所以需要先將.item取出再組成數(shù)組返回
? ?}
? ?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[]{};
? ? ? ?//根結(jié)點(diǎn)沒有兄弟結(jié)點(diǎn)
? ? ? ?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){
? ? ? ? ? ?//當(dāng)n在第一次循環(huán)之前為根結(jié)點(diǎn)時(shí)不執(zhí)行循環(huá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();
? ? ? ?//傳一個(gè)新的容器用于存放子結(jié)點(diǎn)，getAll返回結(jié)點(diǎn)集合，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<>();
? ? ? ?//測(cè)試略
? ?}
}