Tarjan 的 LCA 算法

c++写的Tarjan 的 LCA 算法，最近公共祖先算法，可供算法学习参考

#include “bintree.h“

TreeNode* lowestCommonAncestor（TreeNode* root TreeNode* p TreeNode* q）
{
	if （root == NULL）
		return NULL;
	if （root == p || root == q）
		return root;
	TreeNode *left = lowestCommonAncestor（root->leftchild p q）;
	TreeNode *right = lowestCommonAncestor（root->rightchild p q）;
	if （left&&right）
	{//p or q on both side of root
		return root;
	}
	return left ? left : right;
}

int main（）
{
	TreeNode *t  *p *q  *lca;
	ElementType pd qd;
	t = create_bitree（）; /*20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 22 -1 -1*/
	pre_order_traversal（t）;
	printf（“\n“）;
	while （1）
	{/*循环为测试使用，交作业可以删掉*/
		scanf（“%d%d“ &pd &qd）;
		if （!（p = pre_order_search（t pd）））
		{
			printf（“%d is not in tree\n“ pd）; break;
		}
		if （!（q = pre_order_search（t qd）））
		{
			printf（“%d is not in tree\n“ qd）; break;
		}
		lca = lowestCommonAncestor（t p q）;
			printf（“lca: %d\n“ lca->data）;
	}
	system（“pause“）;
	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        1158  2018-05-18 10:35  bintree.h
     文件         980  2018-05-18 10:20  main.c
     文件         249  2018-05-18 11:11  readme.txt
     文件        4066  2018-05-18 10:06  测试结果.png