使用C语言求二叉树结点的最低公共祖先的方法

概述算法分析我们直接来分析O(n)的算法。比如求节点F和节点H的最低公共祖先，先求出从根节点A到F的路径，再求出A到H的路径，那么最后一个相同的节点就是最低公共祖先。A->B->D->F和A->B->E->H，最

算法分析

我们直接来分析O(n)的算法。

比如求节点F和节点H的最低公共祖先，先求出从根节点A到F的路径，再求出A到H的路径，那么最后一个相同的节点就是最低公共祖先。A->B->D->F和A->B->E->H，最后相同的节点事B，所以最低公共祖先是B节点。求根节点到指定节点的算法先前已经更新过了，复杂度是O(n)，所以总的时间复杂度是O(n)。
条件细化：
(1)树如果是二叉树，而且是二叉排序树。
             这中条件下可以使用二叉排序树的搜索功能找到最低公共祖先。
(2)树不是二叉排序树，连二叉树都不是，就是普通的树。
      1，如果树中有指向父节点的指针。
              这问题可以将问题转化为两个链表相交，求两个链表的第一个交点。
      2，如果树中没有指向父节点的指针。
              这问题就有点麻烦了。
      
      
具体来看获取从根节点到指定节点的函数代码：

struct BinaryNode{ char value; BinaryNode *left; BinaryNode *right;};

求跟节点到指定节点路径：

bool GetNodePath(BinaryNode *pRoot,BinaryNode *pNode,vector<BinaryNode*> &v){ if(pRoot==NulL)  return false; v.push_back(pRoot); if(pRoot==pNode)  return true; bool found=GetNodePath(pRoot->left,pNode,v); if(!found)  found=GetNodePath(pRoot->right,v); if(!found)  v.pop_back();}

求最低公共祖先节点：

BinaryNode* GetCommonParent(BinaryNode *pRoot,BinaryNode *pNode1,BinaryNode *pNode2){ if(pRoot==NulL || pNode1==NulL || pNode2==NulL)  return NulL; vector<BinaryNode*> v1,v2; GetNodePath(pRoot,pNode1,v1); GetNodePath(pRoot,pNode2,v2); BinaryNode *pLast=pRoot; vector<BinaryNode*>::iterator ite1=v1.begin(); vector<BinaryNode*>::iterator ite2=v2.begin(); while(ite1!=v1.end() && ite2!=v2.end()) {  if(*ite1==*ite2)   pLast=*ite1;  ite1++;  ite2++; } return pLast;}

来看一道具体的ACM题目

    题目描述： 
    给定一棵树，同时给出树中的两个结点，求它们的最低公共祖先。

    输入： 
    输入可能包含多个测试样例。 
    对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。 
    其中每个测试样例包括两行，第一行为一个二叉树的先序遍历序列，其中左右子树若为空则用0代替，其中二叉树的结点个数node_num<10000。 
    第二行为树中的两个结点的值m1与m2(0<m1,m2<10000)。 
    输出： 
    对应每个测试案例， 
    输出给定的树中两个结点的最低公共祖先结点的值，若两个给定结点无最低公共祖先，则输出“My God”。 
    样例输入： 
    2 
    1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0 
    6 8 
    1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0 
    6 12 
    样例输出： 
    2 
    My God 

思路
这道题我考虑的思路是

(1)后序遍历的思想,用栈保存到查找点的路径
(2)然后求两个栈第一个公共节点

AC代码

  #include <stdio.h>   #include <stdlib.h>       #define N 7000       typedef struct btree {     struct btree *lchild,*rchild;     int data;   } btree;       typedef struct stack {     int top;     btree* data[N];   } stack;       stack *first,*second;   int oneflag,secflag;       /**    * 根据前序序列递归构建二叉树    */   voID createBtree(btree **t)   {     int data;     scanf("%d",&data);         if (data == 0) {       *t = NulL;     } else {       *t = (btree *)malloc(sizeof(btree));       (*t)->data = data;       createBtree(&(*t)->lchild);       createBtree(&(*t)->rchild);     }   }       /**    * 后序遍历二叉树,构造遍历栈    */   voID postTraverse(btree *t,stack *s,int srcnum,int *flag)   {     if (t != NulL) {       btree *pre;       pre = NulL;           s->data[s->top ++] = t;       while (s->top > 0 || t) {         if (t) {           s->data[s->top ++] = t;           if (t->data == srcnum) {             *flag = 1;             break;           }           t = t->lchild;         } else {           t = s->data[-- s->top];           if (t->rchild == NulL || t->rchild == pre) {             pre = t;             t = NulL;           } else {             s->data[s->top ++] = t;             t = t->rchild;           }         }       }     }   }       /**    * 查找两个栈第一个公共元素    *    * T = O(n)    *    */   voID stackCommonData(stack *f,stack *s)   {     int top,data,flag;         top = (f->top > s->top) ? s->top : f->top;         while (top > 0) {       if (f->data[top - 1]->data == s->data[top - 1]->data) {         data = f->data[top - 1]->data;         flag = 1;         break;       } else {         top --;       }     }         if (flag) {       printf("%d\n",data);     } else {       printf("My God\n");     }   }       /**    * 清理二叉树    *    */   voID cleanBtree(btree *t)   {     if (t) {       cleanBtree(t->lchild);       cleanBtree(t->rchild);       free(t);     }   }           int main(voID)   {     int n,sf,se;     btree *t;         scanf("%d",&n);     while (n --) {       createBtree(&t);       scanf("%d %d",&sf,&se);               first = (stack *)malloc(sizeof(stack));       first->top = 0;       oneflag = 0;       postTraverse(t,first,&oneflag);           second = (stack *)malloc(sizeof(stack));       second->top = 0;       secflag = 0;       postTraverse(t,second,se,&secflag);           if (oneflag == 0 || secflag == 0 || first->top == 0 || second->top == 0) {         printf("My God\n");         cleanBtree(t);         continue;       } else {         stackCommonData(first,second);         cleanBtree(t);       }     }     return 0;   } 

    /**************************************************************
        Problem: 1509
        User: wangzhengyi
        Language: C
        Result: Accepted
        Time:150 ms
        Memory:110212 kb
    ****************************************************************/ 

总结

以上是内存溢出为你收集整理的使用C语言求二叉树结点的最低公共祖先的方法全部内容，希望文章能够帮你解决使用C语言求二叉树结点的最低公共祖先的方法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。