LCA （Lowest Common Ancestor)
一篇轉(zhuǎn)載的文章，是對(duì)于二叉搜索樹的算法
http://blog.csdn.net/AmiRural/archive/2006/06/07/777966.aspx
[題目]：已知二元搜索樹（Binary Search Tree）上兩個(gè)結(jié)點(diǎn)的值，請(qǐng)找出它們的公共祖先。你可以假設(shè)這兩個(gè)值肯定存在。這個(gè)函數(shù)的調(diào)用接口如下所示：
int FindLowestCommonAncestor(node *root, int value1, int value2);
根據(jù)樹的存儲(chǔ)結(jié)構(gòu)，我們可以立刻得到一個(gè)這樣的算法：從兩個(gè)給定的結(jié)點(diǎn)出發(fā)回溯，兩條回溯路線的交點(diǎn)就是我們要找的東西。這個(gè)算法的具體實(shí)現(xiàn)辦法是：從根
結(jié)點(diǎn)開始，先用這兩個(gè)結(jié)點(diǎn)的全體祖先分別生成兩個(gè)鏈表，再把這兩個(gè)鏈表第一次出現(xiàn)不同結(jié)點(diǎn)的位置找出來，則它們的前一個(gè)結(jié)點(diǎn)就是我們要找的東西。
這個(gè)算法倒沒有什么不好的地方，但是它沒有利用二元搜索樹的任何特征，其他類型的樹也可以用這個(gè)算法來處理。二元搜索樹中左結(jié)點(diǎn)的值永遠(yuǎn)小于或者等于當(dāng)前
結(jié)點(diǎn)的值，而右結(jié)點(diǎn)的值永遠(yuǎn)大于或者等于當(dāng)前結(jié)點(diǎn)的值。仔細(xì)研究，4和14的最低公共祖先是8，它與4和14的其他公共祖先是有重要區(qū)別的：其他的公共祖
先或者同時(shí)大于4和4，或者同時(shí)小于4和14，只有8介于4和14之間。利用這一研究成果，我們就能得到一個(gè)更好的算法。
從根結(jié)點(diǎn)出發(fā)，沿著兩個(gè)給定結(jié)點(diǎn)的公共祖先前進(jìn)。當(dāng)這兩個(gè)結(jié)點(diǎn)的值同時(shí)小于當(dāng)前結(jié)點(diǎn)的值時(shí)，沿當(dāng)前結(jié)點(diǎn)的左指針前進(jìn)；當(dāng)這兩個(gè)結(jié)點(diǎn)的值同時(shí)大于當(dāng)前結(jié)點(diǎn)的
值時(shí)，沿當(dāng)前結(jié)點(diǎn)的右指針前進(jìn)；當(dāng)?shù)谝淮斡龅疆?dāng)前結(jié)點(diǎn)的值介于兩個(gè)給定的結(jié)點(diǎn)值之間的情況時(shí)，這個(gè)當(dāng)前結(jié)點(diǎn)就是我們要找的最的最低公共祖先了。
這是一道與樹有關(guān)的試題，算法也有遞歸的味道，用遞歸來實(shí)現(xiàn)這一解決方案似乎是順理成章的事，可這里沒有這個(gè)必要。遞歸技術(shù)特別適合于對(duì)樹的多個(gè)層次進(jìn)行
遍歷或者需要尋找某個(gè)特殊結(jié)點(diǎn)的場合。這道題只是沿著樹結(jié)點(diǎn)逐層向下前進(jìn)，用循環(huán)語句來實(shí)現(xiàn)有關(guān)的過程將更簡單明了。
int FindLowestCommonAncestor(node *root, int value1, int value2)
{
node *curnode = root;
while(1)
{
if (curnode->data>value1&&curnode->data>value2)
curnode = curnode->left;
else if(curnode->data<value1&&curnode->data<value2)
curnode = curnode->right;
else
return curnode->data;
}
}
C語言實(shí)現(xiàn)：
/*二叉排序樹的生成及樹，任意兩結(jié)點(diǎn)的最低公共祖先 Amirural設(shè)計(jì)*/
#include <stdio.h>
#define null 0
int counter=0;
typedef struct btreenode
{int data;
struct btreenode *lchild;
struct btreenode *rchild;
}bnode;
bnode *creat(int x,bnode *lbt,bnode *rbt) //生成一棵以x為結(jié)點(diǎn)，以lbt和rbt為左右子樹的二叉樹
{bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p, int x) //x作為左孩子插到二叉樹中
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->lchild!=null) //若p有左孩子，則將原來的左孩子作為結(jié)點(diǎn)x的右孩子
q->rchild=p->lchild;
p->lchild=q;
}
return(p);
}
bnode *ins_rchild(bnode *p, int x) //x作為右孩子插入到二叉樹
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->rchild!=null) //若x有右孩子，則將原來的右孩子作為結(jié)點(diǎn)x的的左孩子
q->lchild=p->rchild;
p->rchild=q;
}
return(p);
}
void prorder(bnode *p)
{if(p==null)
return;
printf("%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild);
if(p->lchild!=null)
prorder(p->lchild);
if(p->rchild!=null)
prorder(p->rchild);
}
void print(bnode *p) //嵌套括號(hào)表示二叉樹，輸出左子樹前打印左括號(hào)，
{ //輸出右子樹后打印右括號(hào)。
if(p!=null)
{printf("%d",p->data);
if(p->lchild!=null||p->rchild!=null)
{printf("(");
print(p->lchild);
if(p->rchild!=null)
printf(",");
print(p->rchild);
printf(")");
}
}
}
int FindLowestCommonAncestor(bnode *root, int value1, int value2)
{
bnode *curnode = root;
while(1)
{
if (curnode->data>value1&&curnode->data>value2)
curnode = curnode->lchild;
else if(curnode->data<value1&&curnode->data<value2)
curnode = curnode->rchild;
else
return curnode->data;
}
}
main()
{
bnode *bt,*p,*q;
int x,y,v1,v2;
printf("輸入根結(jié)點(diǎn)：");
scanf("%d",&x);
p=creat(x,null,null);
bt=p; //使bt p都指向根結(jié)點(diǎn)
printf("輸入新的結(jié)點(diǎn)值：");
scanf("%d",&x);
while(x!=-1)
{p=bt;
q=p;
while(x!=p->data&&q!=null) //q記錄當(dāng)前根結(jié)點(diǎn)
{p=q;
if(x<p->data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{printf("元素%d已經(jīng)插入二叉樹中！\n",x);
}
else
if(x<p->data) ins_lchild(p,x);
else ins_rchild(p,x);
scanf("%d",&x);
}
p=bt;
printf("struct of the binary tree:\n");
printf("number\taddress\tdata\tlchild\trchild\n");
prorder(p);
printf("\n");
printf("用括號(hào)形式輸出二叉樹:");
print(p);
printf("\n請(qǐng)任意輸入樹中存在的兩個(gè)結(jié)點(diǎn):");
scanf("%d,%d",&v1,&v2);
y = FindLowestCommonAncestor(p, v1, v2);
printf("輸出%d和%d的最低公共祖先：",v1,v2);
printf("%d\n",y);
}
運(yùn)行結(jié)果：
輸入根結(jié)點(diǎn)：20
輸入新的結(jié)點(diǎn)值：8 22 4 12 10 14 -1 （以-1結(jié)束結(jié)點(diǎn)的輸入）
struct of the binary tree:
number addresss data lchild rchild
1 4391168 20 4391104 4391040
2 4391104 8 4390976 4399072
3 4390976 4 0 0
4 4399072 12 4399008 4398944
5 4399008 10 0 0
6 4398644 14 0 0
7 4391040 22 0 0
用括號(hào)形式輸出：20(8(4,12(10,14)),22) （輸出左子樹打印左括號(hào)，輸出右子樹后打印括號(hào)）
請(qǐng)任意輸入樹中存在的兩個(gè)結(jié)點(diǎn)：4，14
輸出4和14的最低祖先：8