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

多叉树

多叉树，单个节点Node数据结构，大概如下：

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

intvalue;

List<Node>child_list;

};

函数输入：多叉树的两个节点X、Y

函数输出：找到X和Y最短路径，打印输长度和节点。

举例: （右图）

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

输出结果为” 5: G->B->F->N->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>();

        

         Achild_list.add(B);

         Achild_list.add(C);

         Achild_list.add(D);

         A.setChild_list(Achild_list);

        

         Bchild_list.add(E);

         Bchild_list.add(F);

         Bchild_list.add(G);

         B.setChild_list(Bchild_list);

        

         Dchild_list.add(H);

         Dchild_list.add(I);

         Dchild_list.add(J);

         D.setChild_list(Dchild_list);

        

         Fchild_list.add(K);

         Fchild_list.add(L);

         Fchild_list.add(N);

         F.setChild_list(Fchild_list);

        

         Hchild_list.add(O);

         Hchild_list.add(P);

         Hchild_list.add(Q);

         H.setChild_list(Hchild_list);

        

         Nchild_list.add(R);

         Nchild_list.add(S);

         Nchild_list.add(T);

         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--)

                       shortestRoute.add(y.get(i));

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

                       shortestRoute.add(x.get(j));

                   break;

              }else{

                   times++;

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

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

                            shortestRoute.add(y.get(i));

                       shortestRoute.add(top);

                       for(NodexNode : x)

                            shortestRoute.add(xNode);

                   }

              }

         }

         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()){   //判断是否找到目标节点，若找到直接返回

                       result.add(x);

                       return result;

                   }

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

                       result.add(n);   //添加路径节点

                       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 向上某一层有同一个父节点

          * 该思路自己实现吧

          */

    

}