應用C說話求二叉樹結點的最低公共先人的辦法。本站提示廣大學習愛好者：（應用C說話求二叉樹結點的最低公共先人的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是應用C說話求二叉樹結點的最低公共先人的辦法正文
算法剖析
我們直接來剖析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,pNode,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, sf, &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
****************************************************************/
