算法分析
我们直接来分析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语言求二叉树结点的最低公共祖先的方法所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)