App下載

使用Java如何實(shí)現(xiàn)樹(shù)的同構(gòu)?

猿友 2021-06-22 16:24:53 瀏覽數(shù) (2079)
反饋

今天給大家?guī)?lái)的是如何使用Java如何實(shí)現(xiàn)樹(shù)的同構(gòu),希望能夠給你們提供一些思路。
給定兩棵樹(shù)r1、r2,如果r1可以通過(guò)若干次的左子樹(shù)和右子樹(shù)互換,使之與r2完全相同,這說(shuō)明兩者同構(gòu)。

舉例


樹(shù)的構(gòu)造

樹(shù)可以由數(shù)組或鏈表來(lái)構(gòu)造:舉例:上圖左上角的樹(shù)通過(guò)數(shù)組可表示為

0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E G - - - F - H -

該方式浪費(fèi)了部分空間,但適合表示完全二叉樹(shù)

鏈表方式則比較直觀

除上述兩種方式外,還可以采用“類(lèi)數(shù)組”的方式

  1. public static class Node{
  2. String data;
  3. int left;
  4. int right;
  5. }

舉例:上圖左上角的樹(shù)可表示為

數(shù)組索引 data left right
0 A 1 2
1 B 3 4
2 C 6 -
3 D - -
4 E 5 -
5 F - -
6 G 7 -
7 H - -

本文的樹(shù)結(jié)構(gòu)使用了第三種方式

終端輸入:

A,1,2B,3,-C,-,-D,-,-A,2,1B,3,-C,-,-D,-,-
  1. public class TongGou {
  2. private Scanner scanner;
  3. public TongGou(){
  4. scanner = new Scanner(System.in);
  5. }
  6. //樹(shù)結(jié)構(gòu)
  7. public static class Node{
  8. String data;
  9. int left;
  10. int right;
  11. }
  12. /**
  13. * 創(chuàng)建樹(shù)
  14. * @param nodes
  15. * @return
  16. */
  17. public int createTree(Node[] nodes){
  18. int N = nodes.length;
  19. int root = -1;
  20. int[] check = new int[N];
  21. Arrays.fill(check,0); //初始化為0
  22. for (int i=0;i<N;i++){
  23. //輸入格式 data,left,right
  24. String next = scanner.next();
  25. String[] inputList = next!=null?next.split(","):null;
  26. if(inputList!=null&&inputList.length==3){
  27. nodes[i] = new Node();
  28. int left = "-".equals(inputList[1])?-1:Integer.parseInt(inputList[1]);
  29. int right = "-".equals(inputList[2])?-1:Integer.parseInt(inputList[2]);
  30. nodes[i].data = inputList[0];
  31. nodes[i].left = left;
  32. nodes[i].right = right;
  33. if(left>0) {
  34. check[left] = 1;
  35. }
  36. if(right>0){
  37. check[right] = 1;
  38. }
  39. }
  40. }
  41. for(int i=0;i<check.length;i++){
  42. if(check[i]==0&&nodes[i].data!=null){
  43. root = i;
  44. break;
  45. }
  46. }
  47. return root;
  48. }
  49. /**
  50. * 判斷同構(gòu)
  51. * @param r1
  52. * @param r2
  53. * @return
  54. */
  55. public boolean isomorphic(int r1,int r2,Node[] t1,Node[] t2){
  56. //須注意不要漏掉邏輯!
  57. //兩個(gè)根節(jié)點(diǎn)均為null,必同構(gòu)
  58. if ((r1 == -1) && (r2 == -1)) {
  59. return true;
  60. }
  61. //一個(gè)非空 另一個(gè)空,必不同構(gòu)
  62. if(((r1==-1)&&(r2!=-1))||((r1!=-1)&&(r2==-1))){
  63. return false;
  64. }
  65. //兩個(gè)節(jié)點(diǎn)非空 但值不同,必不同構(gòu)
  66. if(!t1[r1].data.equals(t2[r2].data)){
  67. return false;
  68. }
  69. //兩根節(jié)點(diǎn)的左孩子為空條件下,則須判斷兩根節(jié)點(diǎn)的右子樹(shù)是否同構(gòu)
  70. if(t1[r1].left==-1&&t2[r2].left==-1){
  71. return isomorphic(t1[r1].right,t2[r2].right,t1,t2);
  72. }
  73. //兩根節(jié)點(diǎn)的左孩子不為空且左孩子的值也相同,須判斷兩根節(jié)點(diǎn)的左子樹(shù)是否同構(gòu)以及兩根節(jié)點(diǎn)的右子樹(shù)是否同構(gòu)
  74. //如果左右子樹(shù)均同構(gòu),則整棵樹(shù)同構(gòu)
  75. if((t1[r1].left!=-1&&t2[r2].left!=-1)&&(t1[t1[r1].left].data.equals(t2[t2[r2].left].data))){
  76. return isomorphic(t1[r1].left,t2[r2].left,t1,t2)&&isomorphic(t1[r1].right,t2[r2].right,t1,t2);
  77. }else{
  78. //分兩種情況解釋?zhuān)?/li>
  79. //1、兩根節(jié)點(diǎn)的左孩子不為空,但左孩子的值不同
  80. //例如:t1[r1.left].data!=t2[r2.left].data。但有t1[r1.left].data==t2[r2.right].data、t1[r1.right].data==t2[r2.left].data
  81. //即有可能r1的左子樹(shù)與r2的右子樹(shù)同構(gòu)、r1的右子樹(shù)與r2的左子樹(shù)同構(gòu)
  82. //故須判斷r1的左子樹(shù)是否與r2的右子樹(shù)同構(gòu),以及r1的右子樹(shù)是否與r2的左子樹(shù)同構(gòu)
  83. //2、兩根節(jié)點(diǎn)的左孩子一個(gè)為空,一個(gè)不為空
  84. //例如:r1.left==-1、r2.left!=-1,如果r2.right==-1,顯然r1的左子樹(shù)與r2的右子樹(shù)同構(gòu),此時(shí)則有可能r1的右子樹(shù)與r2的左子樹(shù)同構(gòu)
  85. //故須判斷r1的左子樹(shù)是否與r2的右子樹(shù)同構(gòu),以及r1的右子樹(shù)是否與r2的左子樹(shù)同構(gòu)
  86. return isomorphic(t1[r1].left,t2[r2].right,t1,t2)&&isomorphic(t1[r1].right,t2[r2].left,t1,t2);
  87. }
  88. }
  89. public static void main(String[] args) {
  90. TongGou tongGou = new TongGou();
  91. Node[] nodes = new Node[4];
  92. Node[] nodes1 = new Node[4];
  93. int tree1 = tongGou.createTree(nodes);
  94. System.out.println();
  95. int tree2 = tongGou.createTree(nodes1);
  96. boolean isomorphic = tongGou.isomorphic(tree1, tree2, nodes, nodes1);
  97. System.out.println(isomorphic);
  98. }
  99. }

到此這篇關(guān)于Java如何實(shí)現(xiàn)樹(shù)的同構(gòu)?的文章就介紹到這了。


0 人點(diǎn)贊