现在的位置: 首页 > 综合 > 正文

公共父节点

2018年12月14日 ⁄ 综合 ⁄ 共 10885字 ⁄ 字号 小 中 大 ⁄ 评论关闭

转自：http://blog.csdn.net/tianliang0123/article/details/7172396

二叉查找树

如果该二叉树是二叉查找树，那么求解LCA十分简单。

基本思想为：从树根开始，该节点的值为t，如果t大于t1和t2，说明t1和t2都位于t的左侧，所以它们的共同祖先必定在t的左子树中，从t.left开始搜索；如果t小于t1和t2，说明t1和t2都位于t的右侧，那么从t.right开始搜索；如果t1<t< t2，说明t1和t2位于t的两侧，那么该节点t为公共祖先。

如果t1是t2的祖先，那么应该返回t1的父节点；同理，如果t2是t1的祖先，应该返回t2的父节点。

Java代码

 

[java] view
plaincopy

  1. public int query(Node t1, Node t2, Node t) {  
  2.     int left = t1.value;  
  3.     int right = t2.value;  
  4.     Node parent = null;  
  5.           
  6.     if (left > right) {  
  7.         int temp = left;  
  8.         left = right;  
  9.         right = temp;  
  10.     }  
  11.           
  12.     while (true) {  
  13.         if (t.value < left) {  
  14.             parent = t;  
  15.             t = t.right;  
  16.         } else if (t.value > right) {  
  17.             parent = t;  
  18.             t = t.left;  
  19.         } else if (t.value == left || t.value == right) {  
  20.             return parent.value;  
  21.         } else {  
  22.             return t.value;  
  23.         }  
  24.     }  
  25. }  

 

[java] view
plaincopy

  1. 1.public int query(Node t1, Node t2, Node t) {    
  2. 2.    int left = t1.value;    
  3. 3.    int right = t2.value;    
  4. 4.    Node parent = null;    
  5. 5.            
  6. 6.    if (left > right) {    
  7. 7.        int temp = left;    
  8. 8.        left = right;    
  9. 9.        right = temp;    
  10. 10.    }    
  11. 11.            
  12. 12.    while (true) {    
  13. 13.        if (t.value < left) {    
  14. 14.            parent = t;    
  15. 15.            t = t.right;    
  16. 16.        } else if (t.value > right) {    
  17. 17.            parent = t;    
  18. 18.            t = t.left;    
  19. 19.        } else if (t.value == left || t.value == right) {    
  20. 20.            return parent.value;    
  21. 21.        } else {    
  22. 22.            return t.value;    
  23. 23.        }    
  24. 24.    }    
  25. 25.}    

    其中，parent用于处理t1是t2的祖先（或t2是t1的祖先）的情况。

一般的二叉树

如果二叉树不是二叉查找树该怎么办呢？

 

1. 离线算法(Tarjan)

利用并查集优越的时空复杂度，可以实现O(n+q)的算法，q是查询次数。

Tarjan算法基于深度优先搜索。对于新搜索到的一个结点u，先创建由u构成的集合，再对u的每颗子树进行搜索，每搜索完一棵子树，这时候子树中所有的结点的最近公共祖先就是u了。

Cpp代码

 

[cpp] view
plaincopy

  1. void LCA(int parent)       //从根节点开始  
  2. {  
  3.     p[parent] = parent;  
  4.     ancestor[findSet(parent)] = parent;  
  5.     for(int i = index[parent]; i != -1; i = e[i].next)  
  6.     {  
  7.         LCA(e[i].to);  
  8.         Union(parent,e[i].to);  
  9.         ancestor[findSet(parent)] = parent;  
  10.     }  
  11.     vis[parent] = true;  
  12.     if(parent == a && vis[b])   //要先将所有查询记录下来，这里只有一个查询：a与b的LCA  
  13.         printf("%d\n",ancestor[findSet(b)]);  
  14.     else if(parent == b && vis[a])  
  15.         printf("%d\n",ancestor[findSet(a)]);  
  16. }  

 

[java] view
plaincopy

  1. 1.void LCA(int parent)       //从根节点开始    
  2. 2.{    
  3. 3.    p[parent] = parent;    
  4. 4.    ancestor[findSet(parent)] = parent;    
  5. 5.    for(int i = index[parent]; i != -1; i = e[i].next)    
  6. 6.    {    
  7. 7.        LCA(e[i].to);    
  8. 8.        Union(parent,e[i].to);    
  9. 9.        ancestor[findSet(parent)] = parent;    
  10. 10.    }    
  11. 11.    vis[parent] = true;    
  12. 12.    if(parent == a && vis[b])   //要先将所有查询记录下来，这里只有一个查询：a与b的LCA    
  13. 13.        printf("%d\n",ancestor[findSet(b)]);    
  14. 14.    else if(parent == b && vis[a])    
  15. 15.        printf("%d\n",ancestor[findSet(a)]);    
  16. 16.}    

2. 在线算法(RMQ)

一个O(nlog2n)的预处理，O(1)的查询。

以下面一棵树为例：

           (1)
         /     \
       (2)     (7)
      /   \       \
    (3)  (4)     (8)
          /   \
         (5)  (6)

step1：


    按深度遍历树，记录访问顺序和相应的深度(2*n-1)，及每个节点第一次出现的位置。


    结点的访问顺序为:1 2 3 24 5 4 6 4 2 1 7 8 7
    相应的深度为：    0 1 2 1 2 3 2 3 2 1 0 1 2 1 0
    结点1-8第一次出现的次序为：1 2 3 5 6 8 12 13

step2：

    查询3和6的公共祖先，考虑3和6第一次出现的位置为3和8，即寻找序列2 1 2 3 2 3中的最小值，最小值为1，对应的点位2，则3与6的最近公共祖先为2。

step3：

    则对于给出的任意两个结点，找出它们第一次出现的位置i,j(i<j)，在深度序列中查询最小值的下标k，depth[k]即为所求。显然，查询多次深度序列中的最小值的下标，自然而然就想到了RMQ。

Java代码

 

[java] view
plaincopy

  1. 1.public class LCA {    
  2. 2.        
  3. 3.    private final int MAX = 10;    
  4. 4.    private int[] dfs = new int[2*MAX];    
  5. 5.    private int[] depth = new int[2*MAX];    
  6. 6.    private int[][] f;    
  7. 7.    private int[] call = new int[MAX];    
  8. 8.    private int len = 0;    
  9. 9.        
  10. 10.    public void track(Node t, int d) {    
  11. 11.        if (t == null)    
  12. 12.            return;    
  13. 13.        dfs[len] = t.value;    
  14. 14.        depth[len] = d;    
  15. 15.        call[t.value-1] = len;    
  16. 16.        len++;    
  17. 17.            
  18. 18.        track2(t.left, d+1);    
  19. 19.        if (t.left != null) {    
  20. 20.            dfs[len] = t.value;    
  21. 21.            depth[len] = d;    
  22. 22.            len++;    
  23. 23.        }    
  24. 24.            
  25. 25.        track2(t.right, d+1);    
  26. 26.        if (t.right != null) {    
  27. 27.            dfs[len] = t.value;    
  28. 28.            depth[len] = d;    
  29. 29.            len++;    
  30. 30.        }    
  31. 31.    }    
  32. 32.        
  33. 33.    public void rmq() {    
  34. 34.        int count = 1;    
  35. 35.        while ((1 << count) <= len)    
  36. 36.            count++;    
  37. 37.        f = new int[len][count];    
  38. 38.        count--;    
  39. 39.            
  40. 40.        for (int i = 0; i < len; i++) {    
  41. 41.            f[i][0] = i;    
  42. 42.        }    
  43. 43.            
  44. 44.        for (int j = 1; (1 << j) <= len; j++) {    
  45. 45.            for (int i = 0; i+(1<<j)-1 < len; i++) {    
  46. 46.                f[i][j] = depth[f[i][j-1]] < depth[f[i+(1<<j-1)][j-1]] ?     
  47. 47.                        f[i][j-1] : f[i+(1<<j-1)][j-1];    
  48. 48.            }    
  49. 49.        }    
  50. 50.    }    
  51. 51.        
  52. 52.    public int query(Node t1, Node t2) {    
  53. 53.        int start = call[t1.value-1];    
  54. 54.        int end = call[t2.value-1];    
  55. 55.            
  56. 56.        if(start > end) {    
  57. 57.            int temp = start;    
  58. 58.            start = end;    
  59. 59.            end = temp;    
  60. 60.        }    
  61. 61.            
  62. 62.        int count = 1;    
  63. 63.        while ((1 << count) <= end - start + 1)     
  64. 64.            count++;    
  65. 65.        count--;    
  66. 66.        int result = depth[f[start][count]] < depth[f[end-(1<<count)+1][count]] ?    
  67. 67.                f[start][count] : f[end-(1<<count)+1][count];    
  68. 68.            
  69. 69.        if (dfs[result] == t1.value || dfs[result] == t2.value) {    
  70. 70.            int temp = depth[result];    
  71. 71.            while (depth[result] >= temp)    
  72. 72.                result--;    
  73. 73.        }    
  74. 74.        return dfs[result];     
  75. 75.    }    
  76. 76.        
  77. 77.    public static void main(String[] args) {    
  78. 78.        Node n3 = new Node(3);    
  79. 79.        Node n5 = new Node(5);    
  80. 80.        Node n6 = new Node(6);    
  81. 81.        Node n4 = new Node(4, n5, n6);    
  82. 82.        Node n2 = new Node(2, n3, n4);    
  83. 83.        Node n8 = new Node(8);    
  84. 84.        Node n7 = new Node(7, null, n8);    
  85. 85.        Node n1 = new Node(1, n2, n7);    
  86. 86.            
  87. 87.        LCA l = new LCA();    
  88. 88.        l.track(n1, 0);    
  89. 89.        l.rmq();    
  90. 90.    
  91. 91.        System.out.println(l.query(n5, n4));        
  92. 92.    }    
  93. 93.}    
  94. 94.    
  95. 95.class Node {    
  96. 96.    int value;    
  97. 97.    Node left;    
  98. 98.    Node right;    
  99. 99.        
  100. 100.    public Node(int value, Node left, Node right) {    
  101. 101.        this.value = value;    
  102. 102.        this.left = left;    
  103. 103.        this.right = right;    
  104. 104.    }    
  105. 105.        
  106. 106.    public Node(int value) {    
  107. 107.        this.value = value;    
  108. 108.        this.left = null;    
  109. 109.        this.right = null;    
  110. 110.    }    
  111. 111.}    


 

[java] view
plaincopy

  1. public class LCA {  
  2.       
  3.     private final int MAX = 10;  
  4.     private int[] dfs = new int[2*MAX];  
  5.     private int[] depth = new int[2*MAX];  
  6.     private int[][] f;  
  7.     private int[] call = new int[MAX];  
  8.     private int len = 0;  
  9.       
  10.     public void track(Node t, int d) {  
  11.         if (t == null)  
  12.             return;  
  13.         dfs[len] = t.value;  
  14.         depth[len] = d;  
  15.         call[t.value-1] = len;  
  16.         len++;  
  17.           
  18.         track2(t.left, d+1);  
  19.         if (t.left != null) {  
  20.             dfs[len] = t.value;  
  21.             depth[len] = d;  
  22.             len++;  
  23.         }  
  24.           
  25.         track2(t.right, d+1);  
  26.         if (t.right != null) {  
  27.             dfs[len] = t.value;  
  28.             depth[len] = d;  
  29.             len++;  
  30.         }  
  31.     }  
  32.       
  33.     public void rmq() {  
  34.         int count = 1;  
  35.         while ((1 << count) <= len)  
  36.             count++;  
  37.         f = new int[len][count];  
  38.         count--;  
  39.           
  40.         for (int i = 0; i < len; i++) {  
  41.             f[i][0] = i;  
  42.         }  
  43.           
  44.         for (int j = 1; (1 << j) <= len; j++) {  
  45.             for (int i = 0; i+(1<<j)-1 < len; i++) {  
  46.                 f[i][j] = depth[f[i][j-1]] < depth[f[i+(1<<j-1)][j-1]] ?   
  47.                         f[i][j-1] : f[i+(1<<j-1)][j-1];  
  48.             }  
  49.         }  
  50.     }  
  51.       
  52.     public int query(Node t1, Node t2) {  
  53.         int start = call[t1.value-1];  
  54.         int end = call[t2.value-1];  
  55.           
  56.         if(start > end) {  
  57.             int temp = start;  
  58.             start = end;  
  59.             end = temp;  
  60.         }  
  61.           
  62.         int count = 1;  
  63.         while ((1 << count) <= end - start + 1)   
  64.             count++;  
  65.         count--;  
  66.         int result = depth[f[start][count]] < depth[f[end-(1<<count)+1][count]] ?  
  67.                 f[start][count] : f[end-(1<<count)+1][count];  
  68.           
  69.         if (dfs[result] == t1.value || dfs[result] == t2.value) {  
  70.             int temp = depth[result];  
  71.             while (depth[result] >= temp)  
  72.                 result--;  
  73.         }  
  74.         return dfs[result];   
  75.     }  
  76.       
  77.     public static void main(String[] args) {  
  78.         Node n3 = new Node(3);  
  79.         Node n5 = new Node(5);  
  80.         Node n6 = new Node(6);  
  81.         Node n4 = new Node(4, n5, n6);  
  82.         Node n2 = new Node(2, n3, n4);  
  83.         Node n8 = new Node(8);  
  84.         Node n7 = new Node(7, null, n8);  
  85.         Node n1 = new Node(1, n2, n7);  
  86.           
  87.         LCA l = new LCA();  
  88.         l.track(n1, 0);  
  89.         l.rmq();  
  90.   
  91.         System.out.println(l.query(n5, n4));      
  92.     }  
  93. }  
  94.   
  95. class Node {  
  96.     int value;  
  97.     Node left;  
  98.     Node right;  
  99.       
  100.     public Node(int value, Node left, Node right) {  
  101.         this.value = value;  
  102.         this.left = left;  
  103.         this.right = right;  
  104.     }  
  105.       
  106.     public Node(int value) {  
  107.         this.value = value;  
  108.         this.left = null;  
  109.         this.right = null;  
  110.     }  
  111. }  

3. 后序遍历

基本思想：如果这两个节点不在一条线上（即这两个节点不存在一个节点是另一个节点的祖先的情况），则它们必定分别在所求节点A的左子树和右子树上，后序遍历到第一个满足这个条件的节点就是所要求的节点A。否则，当这两个节点在一条线上，所求节点A则是这两个节点中深度最低的节点的父节点。

Cpp代码

 lca只要能在以root为头结点的子树中找到va或者vb则返回true

[java] view
plaincopy

  1. 1.bool lca(Node *root, int va, int vb, Node *&result, Node* parent)
     //只要有一个目标节点在root的分支中，返回true  
  2. 2.{    
  3. 3.    // left/right 左/右子树是否含有要判断的两节点之一     
  4. 4.    bool left = false, right = false;    
  5. 5.    if (!result && root->left) left = lca(root->left,va,vb,result,root);    
  6. 6.    if (!result && root->right) right = lca(root->right,va,vb,result,root);    
  7. 7.    
  8. 8.    // mid 当前节点是否是要判断的两节点之一     
  9. 9.    bool mid = false;    
  10. 10.    if (root->data == va || root->data == vb) mid=true;    
  11. 11.    if (!result && int(left + right + mid) == 2) {    
  12. 12.        if (mid) result = parent;    
  13. 13.        else result = root;    
  14. 14.    }    
  15. 15.    return left | mid | right ;    
  16. 16.}    
  17. 17.    
  18. 18.Node *query(Node *root,int va, int vb)    
  19. 19.{    
  20. 20.    if (root == NULL) return NULL;    
  21. 21.    Node *result = NULL;    
  22. 22.    lca(root, va, vb,result, NULL);    
  23. 23.    return result;    
  24. 24.}
       
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞