简明现代魔法 -> 计算机算法 -> 二叉树中的最近公共祖先问题

二叉树中的最近公共祖先问题

2011-02-11

题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。

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;  
        }  
    }  
}  

题目:将一个单链表逆转——原来的头指针变为尾指针,原来的尾指针变为头指针。

算法思想:从链表的头结点开始依次逆转,最终将整个链表逆转。

程序代码:

/*节点的类定义*/  
class Node  
{  
    Node * next;  
};  
  
/*链表的类定义*/  
class List  
{  
    Node * head;  
};  
  
/*逆转函数——将一个单链表逆转*/  
void ReverseList(List & list)  
{  
    Node * pre=NULL;  
    Node * cur=list.head;  
    Node * back=cur->next;  
  
    while(back!=NULL)  
    {  
        cur->next=pre;  
        pre=cur;  
        cur=back;  
        back=cur->next;  
    }  
  
}  

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

算法思想:如果一个节点的左子树包含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");   
    }   
}  
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们