7.9*树算法设计和井查集树算法设计7.9.1树分为有根树和无根树有根树中有且仅有一个根结点并且默认树中边（分支）是有向边，也称为有向树。无根树实际上是一个连通无环图，没有根结点，树中的边是无向边。本章中的树默认为有根树，无根树看成无向图，在下一章讨论
树分为有根树和无根树。 有根树中有且仅有一个根结点并且默认树中边（分支）是有向边，也 称为有向树。 无根树实际上是一个连通无环图，没有根结点，树中的边是无向边。 本章中的树默认为有根树，无根树看成无向图，在下一章讨论
1.双亲存储结构2.孩子链存储结构根据问题需要选择合适的存储结构3.孩子兄弟链存储结构
1. 双亲存储结构 2. 孩子链存储结构 3. 孩子兄弟链存储结构 根据问题需要选择合适的存储结构
【例7.24】P0J1330-求树中两个结点的最近公共祖先（LCA）：问题描述：有根树是计算机科学和工程中众所周知的数据结构，下图是一棵有根树。在该图中，每个结点标有1～16的整数。结点8是树的根。如果结点x位于根结点到结点V之间的路径中，则结点x是结点V的祖先。注意这里规定一个结点也是自已的祖先，如结点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。编写一个程序，找到树中两个不同结点的最近公共祖先。101116
【例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个边。每个测试用例的最后一行包含两个不同的整数，需要计算它们的最近公共祖先。输出格式：为每个测试用例输出一行，该行应包含最近公共祖先结点的编号
输入格式：输入由T个测试用例组成。测试用例个数（T）在输入文件 的第一行中给出。每个测试用例以整数N的行开始，整数N是树中的结点数， 2≤N≤10,000。结点用整数1～N标记。接下来的N-1行中的每一行包含一 对表示边的整数，第一个整数是第二个整数的父结点。请注意，具有N个结 点的树具有恰好N-1个边。每个测试用例的最后一行包含两个不同的整数， 需要计算它们的最近公共祖先。 输出格式：为每个测试用例输出一行，该行应包含最近公共祖先结点 的编号
输入样例：2//表示有2个测试用例161/测试用例1的数据1148 510 165 9468 44101.1361510116 710 216 38 1161216 7//求结点16和7的LCA51/测试用例2的数据2 33 4311535//求结点3和5的LCA输出样例：43
输入样例： 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结点的层次1x，y结点的层次ly。（2）若1x≠1y，将较高层次的结点上移直到它们处于相同层次。（3）若x≠y，再将它们同步上移直到x=y。这样的x或者y结点就是LCA。从上述过程看出，主要涉及结点上移操作，为此树采用双亲存储结构较合适。由于结点是通过编号唯一标识的，并且N个结点的编号是1～N，所以直接采用int类型的parent数组作为双亲存储结构，parent[表示结点i的双亲结点编号。那么如何确定根结点呢？任何一个结点i有双亲，则parent[]一定是1～N的整数，为此将parent数组所有元素初始化为-1，如果一个结点的双亲father[为-1，则结点i就是根结点
解：这里的树是有根树，首先由输入创建树存储结构，再对于给定的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就是根结点
101016111611结点16和7的LCA是结点4！
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;1/树的双亲存储结构static int [] parent=new intMAxN];1/求x结点的层次public static int Level(int x) int cnt=o;1/找到根为止while(x!=-1)1/结点x上移{ x=parent[x];1/累计上移的次数就是原×结点的层次cnt++;return cnt;
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 staticintsolve（intx,inty）//求x和y结点的最近公共祖先结点{ int lx=Level(x);//求x结点的层次1xint ly=Level(y);/求y结点的层次1ywhile (lx>ly)//将较高层次的x结点上移{ x=parent[x];1x--;7while (ly>lx)//将较高层次的y结点上移{ y=parent[y];ly--;while (x!=y)//当x和y移到相同层次，再找LCAx=parent[x];y=parent[y];+return x;
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();1/初始化N个结点的双亲为-1for(int i=o;i<=N;i++)parent[i]=-1;1/输入N-1条边，创建双亲存储结构for (int i=l;i<N;i++)1/输入一条边a=fin.nextInt();b=fin.nextInt();parent[b]=a;1/输入查询x=fin.nextInt();心花怒放y=fin.nextInt();//求LCAint ans=solve(x,y);&31/输出结果System.out.println(ans):
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); //输出结果 } } }