# 多叉树-找到X和Y最短路径，打印输长度和节点

xiaoxiao2021-02-28  19

struct Node { //注：只有儿子节点，没父亲节点

intvalue;

List<Node>child_list;

};

G节点到R节点的最短路径为红线所示，

package entity;

import java.util.List;

//注：只有儿子节点，没父亲节点

publicclass Node {

private int value;

private List<Node> child_list;

public Node(){

super();

}

public Node(intvalue){

this.value =value;

}

public int getValue() {

returnvalue;

}

public void setValue(int value) {

this.value =value;

}

public List<Node> getChild_list() {

returnchild_list;

}

public void setChild_list(List<Node> child_list) {

this.child_list =child_list;

}

@Override

public String toString() {

return   (char) value+"";

}

}

package algorithm;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Map.Entry;

import java.util.Set;

import entity.Node;

/**

* 多叉树

* @author lv

*

*/

public class IMultiTree {

public static void main(String[] args) {

Node A = new Node('A');

Node B = new Node('B');

Node C = new Node('C');

Node D = new Node('D');

Node E = new Node('E');

Node F = new Node('F');

Node G = new Node('G');

Node H = new Node('H');

Node I = new Node('I');

Node J = new Node('J');

Node K = new Node('K');

Node L = new Node('L');

Node N = new Node('N');

Node O = new Node('O');

Node P = new Node('P');

Node Q = new Node('Q');

Node R = new Node('R');

Node S = new Node('S');

Node T = new Node('T');

List<Node> Achild_list = new ArrayList<Node>();

List<Node> Bchild_list = new ArrayList<Node>();

List<Node> Dchild_list = new ArrayList<Node>();

List<Node> Fchild_list = new ArrayList<Node>();

List<Node> Hchild_list = new ArrayList<Node>();

List<Node> Nchild_list = new ArrayList<Node>();

A.setChild_list(Achild_list);

B.setChild_list(Bchild_list);

D.setChild_list(Dchild_list);

F.setChild_list(Fchild_list);

H.setChild_list(Hchild_list);

N.setChild_list(Nchild_list);

ArrayList<Node> li1 = new ArrayList<Node>();

ArrayList<Node> list1 = getNodesList(I,A,li1);

ArrayList<Node> li2 = new ArrayList<Node>();

ArrayList<Node> list2 = getNodesList(G,A,li2);

Map<Integer,String> map = getShortestRoute(list1,list2,A);

Set<Entry<Integer, String>>entrySet = map.entrySet();

for(Entry<Integer,String>entry : entrySet)

System.out.println("step : " + entry.getKey()+"    最短路径 ："+entry.getValue());

}

/**

* 获取最短步数和路径节点

* @param x

* @param y

* @param top

* @return

*/

public static Map<Integer,String> getShortestRoute(ArrayList<Node>x,ArrayList<Node> y,Node top){

ArrayList<Node> shortestRoute = new ArrayList<Node>();    // 临时保存合并后的节点，注意合并节点时的存放顺序问题！

int times= 0;   // 记录集合 x 的遍历次数

for(Node n: x){

if(y.contains(n)){   //遍历集合 x，判断集合 y 中是否包含集合 x 的某一个元素

int xIndex= x.indexOf(n);

int yIndex= x.indexOf(n);

for(int i =y.size()-1; i > yIndex; i--)

for(int j =xIndex; j < x.size(); j++)

break;

}else{

times++;

if(times== x.size()){  // 若遍历完整个集合 x, 集合 y 中不包含 x 的某一个元素，则添加 根元素 top

for(int i = y.size()-1; i >= 0; i--)

for(NodexNode : x)

}

}

}

StringBuilder sb = new StringBuilder();

int count= 0;  //记录遍历次数

for(Node node : shortestRoute){

if(count++ == (shortestRoute.size()-1)) //判断是否是集合中最后一个元素，若不是队尾追加"—>"

sb.append(node.toString());

else

sb.append(node.toString()+"—>");

}

Map<Integer,String> map = new HashMap<Integer,String>();

map.put(shortestRoute.size(),sb.toString());

return map;

}

/**

* 注意：该解题思路是在根节点已知的前提下

* 深度优先检索（前序）

* @param x

* @param top         父节点

* @param result  保存路径节点的集合

* @return

*/

public static ArrayList<Node> getNodesList(Node x,Node top,ArrayList<Node>result){

if(x.toString()== top.toString()){

System.out.println("当前节点");

return null;

}

if(top.getChild_list()!= null){

for(Node n: top.getChild_list()){

if(n.getValue()== x.getValue()){   //判断是否找到目标节点，若找到直接返回

return result;

}

if(n.getChild_list()!= null){  //有子节点的节点

getNodesList(x,n,result);     //将该节点作为父节点参数，递归回调

}

else        //没有子节点的跳过本次循环

continue;

//判断是否找到了 x 节点，若否，则清空所有路径的集合result

if(!result.isEmpty()&& !(x == result.get(result.size()-1))) //1、isEmpty()判断是否已经清空集合防止空指针，

result.remove(result.size()-1);   //2、 result.get()若集合最后一个元素等于x 节点，则移除以后追加的尾元素。

}

return result;

}

return null;

}

/**

*

* 思路二：只有三种可能性：

*      1、x 是 y 下的某一层子节点

*      2、y 是 x 下的某一层子节点

*      3、x 和 y 向上某一层有同一个父节点

* 该思路自己实现吧

*/

}