河池学院：《数据结构》课程电子教案（PPT教学课件）第7章 树和二叉树 7.9 树算法设计和并查集

树分为有根树和无根树。 有根树中有且仅有一个根结点并且默认树中边（分支）是有向边，也 称为有向树。 无根树实际上是一个连通无环图，没有根结点，树中的边是无向边。 本章中的树默认为有根树，无根树看成无向图，在下一章讨论

1. 双亲存储结构 2. 孩子链存储结构 3. 孩子兄弟链存储结构 根据问题需要选择合适的存储结构

【例7.24】POJ1330—求树中两个结点的最近公共祖先（LCA）。 问题描述：有根树是计算机科学和工程中众所周知的数据结构，下图是一棵有 根树。在该图中，每个结点标有1～16的整数。结点8是树的根。如果结点x位于根 结点到结点y之间的路径中，则结点x是结点y的祖先。注意这里规定一个结点也是 自己的祖先，如结点7的祖先有结点8，4，6和7。 如果结点x是结点y和结点z的祖先，则结点x称为两个不同结点y和z的公共祖 先，因此结点8和4是结点16和7的公共祖先。如果x是y和z的共同祖先并且在所有共 同祖先中最接近y和z，则结点x被称为结点y和z的最近公共祖先。因此，结点16和7 的最近公共祖先是结点4，因为结点4比结点8更靠近结点16和7。编写一个程序，找 到树中两个不同结点的最近公共祖先。 8 5 9 6 4 7 10 1 15 11 16 2 3 12 14 13

输入格式：输入由T个测试用例组成。测试用例个数（T）在输入文件 的第一行中给出。每个测试用例以整数N的行开始，整数N是树中的结点数， 2≤N≤10,000。结点用整数1～N标记。接下来的N-1行中的每一行包含一 对表示边的整数，第一个整数是第二个整数的父结点。请注意，具有N个结 点的树具有恰好N-1个边。每个测试用例的最后一行包含两个不同的整数， 需要计算它们的最近公共祖先。 输出格式：为每个测试用例输出一行，该行应包含最近公共祖先结点 的编号

输入样例： 2 //表示有 2个测试用例 16 //测试用例 1的数据 1 14 8 5 10 16 5 9 4 6 8 4 4 10 1 13 6 15 10 11 6 7 10 2 16 3 8 1 16 12 16 7 //求结点16 和 7 的LCA 5 //测试用例 2的数据 2 3 3 4 3 1 1 5 3 5 //求结点 3 和 5 的LCA 输出样例： 43

解：这里的树是有根树，首先由输入创建树存储结构，再对于给定的x和 y结点，求LCA的过程如下： （1）求出x结点的层次lx，y结点的层次ly。 （2）若lx≠ly，将较高层次的结点上移直到它们处于相同层次。 （3）若x≠y，再将它们同步上移直到x=y。这样的x或者y结点就是LCA。 从上述过程看出，主要涉及结点上移操作，为此树采用双亲存储结构较 合适。由于结点是通过编号唯一标识的，并且N个结点的编号是1～N，所以 直接采用int类型的parent数组作为双亲存储结构，parent[i]表示结点i 的双亲结点编号。 那么如何确定根结点呢？任何一个结点i有双亲，则parent[i]一定是 1～N的整数，为此将parent数组所有元素初始化为-1，如果一个结点i的双 亲father[i]为-1，则结点i就是根结点

8 5 9 6 4 7 10 1 15 11 16 2 3 12 14 13 8 5 9 6 4 7 10 1 15 11 16 2 3 12 14 13 -1 结点16和7的LCA是结点4！

import java.util.*; import java.util.Scanner; public class Main { final static int MAXN=10005; static int [] parent=new int[MAXN]; //树的双亲存储结构 public static int Level(int x) //求x结点的层次 { int cnt=0; while(x!=-1) //找到根为止 { x=parent[x]; //结点x上移 cnt++; //累计上移的次数就是原x结点的层次 } return cnt; }

public static int solve(int x,int y) //求x和y结点的最近公共祖先结点 { int lx=Level(x); //求x结点的层次lx int ly=Level(y); //求y结点的层次ly while (lx>ly) //将较高层次的x结点上移 { x=parent[x]; lx-; } while (ly>lx) //将较高层次的y结点上移 { y=parent[y]; ly-; } while (x!=y) //当x和y移到相同层次，再找LCA { x=parent[x]; y=parent[y]; } return x; }

public static void main(String[] args) { Scanner fin = new Scanner(System.in); int T,N,a,b,x,y; T=fin.nextInt(); while (T->0) { N=fin.nextInt(); for (int i=0;i<=N;i++) //初始化N个结点的双亲为-1 parent[i]=-1; for (int i=1;i<N;i++) //输入N-1条边,创建双亲存储结构 { a=fin.nextInt(); //输入一条边 b=fin.nextInt(); parent[b]=a; } x=fin.nextInt(); //输入查询 y=fin.nextInt(); int ans=solve(x,y); //求LCA System.out.println(ans); //输出结果 } } }