免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 6391 | 回复: 14

[算法] 关于在二叉树中求两个节点的最低祖先(lowest ancestor)的算法,请大家多多指教。 [复制链接]

论坛徽章:
0
发表于 2005-11-17 15:01 |显示全部楼层
最近遇到这样一道题,下来做了一下。
我的想法是这样的:这个题目的实质就是找到二叉树中的一个节点,以该节点,假定为root,为根的树同时包含这两个目标节点,并且以root->pLeft 和 root->pRight为根的树都不同时包含这两个节点,root 即为所求,算法复杂度为n+(n-1)+(n-2)+... = O(n^2)。

我想请大家看看有没有更高效,更简洁一些的方法呢,请多指教,多谢了
我再补充点哈,我觉得我现在写这个代码感觉不爽,所以我还想看看就算是上面同样的算法,大家有没有一些稍微漂亮点的代码。



  1. /*******************/
  2.   * BinTree structer        *
  3. /*******************/
  4. typedef struct BinTree {
  5.     int key;
  6.     struct BinTree *pLeft;
  7.     struct BinTree *pRight;
  8. }BinTree;

  9. /* Find the lowest common ancestor of pNode1,pNode2 in bin-tree by the*/
  10. / *                 name of root,return the pointer to the ancestor .*/

  11. BinTree * FindLCAncestor(BinTree *root,BinTree *pNode1,BinTree *pNode2)
  12. {
  13.         BOOL bFlag1,bFlag2;
  14.         BinTree *plcAnc,*pTemp;

  15.         pTemp = root;
  16.         while(pTemp) {
  17.                 plcAnc = pTemp;
  18.                 bFlag1 = bFlag2 = FALSE;
  19.                                 pTemp = InOrder(root->pLeft,pNode1,pNode2,&bFlag1,&bFlag2);
  20.                 if(pTemp) {
  21.                         root = root->pLeft;
  22.                         continue;
  23.                 }else {
  24.                               bFlag1 = bFlag2 = FALSE;
  25.                                           pTemp = InOrder(root->pRight,pNode1,pNode2,&bFlag1,&bFlag2);
  26.                 }
  27.                 if(pTemp) {
  28.                         root = root->pRight;
  29.                         continue;
  30.                 }
  31.                 else

  32.                                return plcAnc;
  33.         }
  34. }

  35. /* check whether the two nodes --pNode1 and pNode2 are in the tree root,
  36. *    if true ,return the pointer to the root, otherwise return NULL. */

  37. BinTree *InOrder(BinTree *root,
  38.                    BinTree *pNode1,BinTree *pNode,
  39.                    BOOL *pFlag1,BOOL *pFlag2)
  40. {

  41.         if(!root)
  42.                 return NULL;
  43.         if(root->pLeft)

  44.         InOrder(root->pLeft,pNode1,pNode2,pFlag1,pFlag2);
  45.         if(root == pNode1)
  46.                 *pFlag1 = TRUE;
  47.         if(root == pNode2)
  48.                 *pFlag2 = TRUE;
  49.         if(root->pRight)

  50.         InOrder(root->pRight,pNode1,pNode2,pFlag1,pFlag2);
  51.         if((*pFlag1) && (*pFlag2))
  52.                 return root;
  53.         else
  54.                 return NULL;
  55.        
  56. }
复制代码

[ 本帖最后由 lisp 于 2005-11-17 15:43 编辑 ]

论坛徽章:
0
发表于 2005-11-17 15:23 |显示全部楼层
您看这样行不行:

在结构中加入一个指向 parent 的指针, 然后从 给定的两个节点往 root 走,得到两条路径. 这两条 path 最终是相交的,我们反过来从 root 走这两条路径,看何时分叉即可.

论坛徽章:
0
发表于 2005-11-17 15:46 |显示全部楼层
原帖由 win_hate 于 2005-11-17 15:23 发表
您看这样行不行:

在结构中加入一个指向 parent 的指针, 然后从 给定的两个节点往 root 走,得到两条路径. 这两条 path 最终是相交的,我们反过来从 root 走这两条路径,看何时分叉即可.

这个题是ms的笔试题,题目没有给出指向PARETN的这个指针。当然加入指向parent得指针的话,按您的方法肯定可以搞定。

论坛徽章:
0
发表于 2005-11-17 16:13 |显示全部楼层
那你遍历这棵树两次,  分别寻找这两个节点, 记下向左走还是向右走的序列, 然后对比.

论坛徽章:
0
发表于 2005-11-17 16:54 |显示全部楼层
原帖由 win_hate 于 2005-11-17 16:13 发表
那你遍历这棵树两次,  分别寻找这两个节点, 记下向左走还是向右走的序列, 然后对比.

多谢多谢,我知道怎么做了,有空把代码写出来。
多谢win_hate多次解惑

论坛徽章:
0
发表于 2005-11-17 17:26 |显示全部楼层
这样做好象好一些, 遍历一次去搜索其中一个节点, 找到后, 搜索其下是否有另一个节点,如果有,已经解决.如果没有,则在逐层返回时在另一个分支中搜索剩余节点.

在极端的情况下,回退到 root 之后就可以不搜索另一边了.

[ 本帖最后由 win_hate 于 2005-11-17 17:28 编辑 ]

论坛徽章:
0
发表于 2005-11-17 17:40 |显示全部楼层
不可行,因为没有父节点的指针

论坛徽章:
0
发表于 2005-11-17 17:41 |显示全部楼层
是递归实现的,总可以退到上一层

论坛徽章:
1
荣誉版主
日期:2011-11-23 16:44:17
发表于 2005-11-17 18:12 |显示全部楼层
分别找到root节点到这两个节点的路径,
最后一个相同的节点就是它们最近的共同祖先。

论坛徽章:
0
发表于 2005-11-17 18:58 |显示全部楼层

有点问题, 不知道你测试过没有

如果一个结点a是另外一个结点b的ancestor结点, 那么
返回的是b而不是a。

稍微考虑一下就知道为什么了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP