二叉樹——查找兩個任意節點的最近祖先

很久沒有用過二叉樹了，最近由於需要用到了，發現很多知識需要鞏固了，中間涉及到一個算法就是找任意兩個節點的最近祖先。通過本人回顧和演算，最終提出了下面一個方法，網上也有很多其他的方式實現，再次僅對自己好幾個小時的工作作個記錄和積累吧！ 程序是用C語言寫的，個人覺得如果用C#實現會更加方便。

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

首先是數據結構定義：

typedef char TElemType;
typedef bool Status;

typedef struct BiTNode{
TElemType data;
struct BiTNode * lchild, * rchild;
}BiTNode, * BiTree;

其次是建樹，用樹的定義，以先序序列遞歸方式建立。

BiTNode * CreateBiTree()
{
char ch;
BiTNode * T;
scanf("%c",&ch);
if(ch=='#')
T = 0;
else
{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;
}

空節點的分隔符本處使用的是“#”，可以用其他字符替代。

查找最近祖先的基本算法是遞歸，對每個節點先判斷是否有直接關聯，都沒有就分別獲得各自的直系父節點，遞歸調用時需要通過兩個節點的深度來判斷下一次調用時用哪個使用父節點。具體實現如下：

//查找兩個節點的最近的公共祖先節點
BiTNode * FindNearestAncestor(BiTNode * root, BiTNode* p1, BiTNode* p2, int h1, int h2)
{
if(!p1 || !p2) return 0;
if (p1 == p2)
{
if (p1 == root) return root;
return p1;
}
if (p1 == p2->lchild || p1 == p2->rchild)
return p2;
if (p2 == p1->lchild || p2 == p1->rchild)
return p1;

if (h1 == h2)
return FindNearestAncestor(
root,
GetParent(root, p1),
GetParent(root, p2),
h1 - 1,
h2 - 1);
else
return FindNearestAncestor(
root,
h1 > h2 ? GetParent(root, p1) : p1,
h1 < h2 ? GetParent(root, p2) : p2,
h1 > h2 ? h1 - 1 : h1,
h1 < h2 ? h2 - 1 : h2);
}

其中GetParent是獲取以root為樹根的樹中p節點的直系父節點，定義如下：

BiTNode * GetParent(BiTNode* root, BiTNode * p)
{
if(!root || p == root) return 0;
if(p == root->lchild || p == root->rchild)
{
return root;
}
else
{
return GetParent(root->lchild, p) == 0 ?
GetParent(root->rchild, p) : GetParent(root->lchild, p);
}
}

在主函數中調用如下：

int main()
{
//測試序列: abc###de##fg###
printf("請輸入前序序列，空節點用‘#’代替：\n");
BiTree tree = CreateBiTree();
BiTNode * node = FindNearestAncestor( tree,
tree->rchild->lchild,
tree->rchild->rchild->lchild,
GetHeight(tree,tree->rchild->lchild),
GetHeight(tree,tree->rchild->rchild->lchild)
);

printf("節點%c和節點%c的最近父節點為：%c\n",
tree->rchild->lchild->data,
tree->rchild->rchild->lchild->data,
node->data);
return 0;
}

上述使用了GetHeight函數，用來獲取給定樹中節點p的高度，這個函數的實現耗費了較多時間，主要是以前都是獲取樹的高度，很少獲取指定節點的高度，其實現如下：

//查找節點p的高度，注意與單純只計算樹的高度不同
int GetHeight(BiTNode* root, BiTNode * p, int h = 1)
{
if (!root) return 0;
if (p == root->lchild || p == root->rchild) return h + 1;
return GetHeight(root->lchild, p, h+1) == 0 ?
GetHeight(root->rchild, p, h+1) : GetHeight(root->lchild, p, h+1);
}

上述測試使用的先序序列為

abc###de##fg###

對應的二叉樹如下：

a

/ \

b d
/ / \

c e f

/

g

結果如下：

僅此記錄，供以後忘記了查閱，同時也希望和大家分享。