查找二叉树公共父节点

《查找二叉树公共父节点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、寻找二叉树中两个节点的最近的公共祖先——迅雷笔试归来分类： C/C++学习笔记2010-10-2810:38 779人阅读 评论(4) 收藏 举报      迅雷的笔试可真让人煎熬啊，题量很大，而且考试时间是三个小时。不过迅雷的题目质量很高，既考查了基础知识又不乏高难的数据结构和算法题目。下面和大家分享两道算法编程题，代码没有在编译器上调试，可能会出现一点小bug，感兴趣的朋友可以编译调试一下。 题目1：将一个单链表逆转——原来的头指针变为尾指针，原来的尾指针变为头指针。算法思想：从链表的头结点

2、开始依次逆转，最终将整个链表逆转。 程序代码：viewplain1./*节点的类定义*/  2.class Node  3.{  4.    Node * next;  5.};  6.  7./*链表的类定义*/  8.class List  9.{  10.    Node * head;  11.};  12.  13./*逆转函数——将一个单链表逆转*/  14.void ReverseList(List & list)  15.{  16.    Node * pre=NULL;  1

3、7.    Node * cur=list.head;  18.    Node * back=cur->next;  19.  20.    while(back!=NULL)  21.    {  1.        cur->next=pre;  2.        pre=cur;  3.        cur=back;  4.        back=cur->next;  5.    }  6.  7.}    题目2：要求寻找二叉树中两个节点的最近的公共祖先，并将其返回。view

4、plain1.class Node  2.{  3.   Node * left;  4.   Node * right;  5.   Node * parent;  6.};  7./*查找p，q的最近公共祖先并将其返回。*/  8.Node * NearestCommonAncestor(Node * p,Node * q);   算法思想：这道题的关键在于每个节点中包含指向父节点的指针，这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent，然后将q的所有父节点依次和p-

5、>parent作比较，如果发现两个节点相等，则该节点就是最近公共祖先，直接将其返回。如果没找到相等节点，则将q的所有父节点依次和p->parent->parent作比较......直到p->parent==root。程序代码：viewplain1.Node * NearestCommonAncestor(Node * root,Node * p,Node * q)  2.{  3.    Node * temp;  4.         while(p!=NULL)  5.    {  6.  

6、      p=p->parent;  1.        temp=q;  2.        while(temp!=NULL)  3.        {  4.            if(p==temp->parent)  5.                return p;  6.            temp=temp->parent;  7.        }  8.    }  9.}  知识拓展：对于第二个二叉树的问题，如果节点中不包含指向父节点的指针应该怎么计算？算法思想

7、：如果一个节点的左子树包含p，q中的一个节点，右子树包含另一个，则这个节点就是p，q的最近公共祖先。程序代码：viewplain1./*查找a，b的最近公共祖先，root为根节点，out为最近公共祖先的指针地址*/  2.int FindNCA(Node* root, Node* a, Node* b, Node** out)   3.{   4.    if( root == null )   5.    {   6.        return 0;   7.    }  8.  9.   

8、 if( root == a 

9、

10、 root == b )  10.    {      11.        return 1;  12.    }  13.  14.    int iLeft = FindNCA(root->left, a, b, out);  15.    if( iLeft == 2 )  16.    {      17.        return 2;  18.    }  19.  20.    int iRight = FindNCA(root->right,