Chinaunix首页 | 论坛 | 博客
  • 博客访问: 282376
  • 博文数量: 40
  • 博客积分: 1807
  • 博客等级: 上尉
  • 技术积分: 350
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-03 15:42
文章分类

全部博文(40)

文章存档

2011年(18)

2010年(20)

2009年(2)

我的朋友

分类: LINUX

2011-02-25 17:04:34

要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。
class Node   
{   
   Node * left;   
   Node * right;   
   Node * parent;   
};   
/*查找p,q的最近公共祖先并将其返回。*/  
Node * NearestCommonAncestor(Node * p,Node * q);  
class Node
{
   Node * left;
   Node * right;
   Node * parent;
};
/*查找p,q的最近公共祖先并将其返回。*/
Node * NearestCommonAncestor(Node * p,Node * q);

算法思想:这道题的关键在于每个节点中包含指向父节点的指针,这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent,然后将q的所有父节点依次和p->parent作比较,如果发现两个节点相等,则该节点就是最近公共祖先,直接将其返回。如果没找到相等节点,则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。



程序代码:

Node * NearestCommonAncestor(Node * root,Node * p,Node * q)
{
    Node * temp;
    while(p!=NULL)
    {
        p=p->parent;
        temp=q;
        while(temp!=NULL)
        {
            if(p==temp->parent)
                return p;
            temp=temp->parent;
        }
    }
}


知识拓展:对于第二个二叉树的问题,如果节点中不包含指向父节点的指针应该怎么计算?

算法思想:如果一个节点的左子树包含p,q中的一个节点,右子树包含另一个,则这个节点就是p,q的最近公共祖先。

程序代码:

/*查找a,b的最近公共祖先,root为根节点,out为最近公共祖先的指针地址*/  
int FindNCA(Node* root, Node* a, Node* b, Node** out)    
{    
    if( root == null )    
    {    
        return 0;    
    }   
 
    if( root == a || root == b )  
    {      
        return 1;  
    }  
 
    int iLeft = FindNCA(root->left, a, b, out);  
    if( iLeft == 2 )  
    {      
        return 2;  
    }  
 
    int iRight = FindNCA(root->right, a, b, out);  
    if( iRight == 2 )  
    {      
        return 2;  
    }  
 
    if( iLeft + iRight == 2 )  
    {     
        *out == root;  
    }  
    return iLeft + iRight;  
}  
 
void main()   
{   
    Node* root = ...;   
    Node* a = ...;   
    Node* b = ...;   
    Node* out = null;   
    int i = FindNCA(root, a, b, &out);   
    if( i == 2 )   
    {   
        printf("Result pointer is %p", out);   
    }   
    else   
    {   
        printf("Not find pointer");   
    }   
阅读(6204) | 评论(0) | 转发(0) |
0

上一篇:hypertable介绍

下一篇:Redis Presharding

给主人留下些什么吧!~~