Chinaunix首页 | 论坛 | 博客
  • 博客访问: 894824
  • 博文数量: 119
  • 博客积分: 2493
  • 博客等级: 大尉
  • 技术积分: 2363
  • 用 户 组: 普通用户
  • 注册时间: 2012-06-03 14:00
文章分类

全部博文(119)

文章存档

2013年(19)

2012年(100)

分类: LINUX

2012-09-17 08:49:07

    求树中两个节点的最低公共祖先,不能说只是一个题目,而应该说是一组题目,不同
条件下的题目是完全不一样的,有时面试官故意把条件说的模棱两可,看应聘者能不能
主动提出问题所在。
----------------------------------------------------------------------------------------------
条件细化:
(1)树如果是二叉树,而且是二叉排序树。
             这中条件下可以使用二叉排序树的搜索功能找到最低公共祖先。
(2)树不是二叉排序树,连二叉树都不是,就是普通的树。
      1,如果树中有指向父节点的指针。
              这问题可以将问题转化为两个链表相交,求两个链表的第一个交点。
      2,如果树中没有指向父节点的指针。
              这问题就有点麻烦了。
----------------------------------------------------------------------------------------------
具体问题的分析与解答。
1,如果树是二叉查找树,求两个树节点的最低公共祖先。

由于二叉查找树是顺序的,所以两个节点的公共祖先一定一个位于祖先的左子树,一个位于
祖先的右子树,所以遍历二叉查找树,如果节点的key值均大于给出的两个节点,则向左走,
如果节点的key值均小于给出的两个节点,则向右走。如果节点的key值位于两个节点key值
之间,则该节点就是两个节点的最低公共祖先。

  1. struct node *least_common_parent(bstree *root,struct node *a,struct node *b)
  2. {
  3.         if (!root || !a || !b)
  4.             return NULL;
  5.         while (root != NULL) {
  6.             if (root->key > a->key && root->key > b->key)
  7.                 root = root->lchild;
  8.             else if (root->key < a->key && root->key < b->key)
  9.                 root = root->rchild;
  10.             else
  11.                 return root;
  12.         }
  13.         return NULL;
  14. }
以上代码没有仔细测试过,但简单地测试过,因为这个测试环境不好建立。
----------------------------------------------------------------------------------------------
1,如果树是普通的树,且树中有指向父节点的指针域,那该如何求两个树节点的最低公共
      祖先。
     问题转化为两个链表的相交问题,求两个链表的第一个交点。

----------------------------------------------------------------------------------------------
         
阅读(3838) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~