大纲1.树的概念1.树的概念
2.树的存储
3.例题
4.树的先序遍历(DFS遍历)
5.例题
6.树的层次遍历(BFS遍历)
7.例题
引入Q:
题目描述 小Z无意中发现了一份家谱，家谱中记录了从小Z爷爷到小Z，共3代人的亲缘关系，请你帮Z科计算一下他有多少堂兄弟（小Z的堂兄弟是指和小Z共一个爷爷，但是不共一个爸爸，为计算方便，给出的家谱图中只包括男性成员） 输入格式 输入中，家庭成员的姓名使用整数编号表示，其中小Z爷爷的编号固定为1； 第一行：三个整数n, m和k，表示家谱中共有n个人，m条血缘关系，小科的编号是k； 接下来m行，每行两个用空格隔开的整数x和y。表示x是y的父亲。 输出格式 一行：一个整数，表示小Z堂兄弟的数量。 输入输出样列 输入样例1： 13 12 9 1 2 1 3 1 4 1 5 2 6 2 7 2 8 3 9 3 10 4 11 5 12 5 13 输出样例1： 6 说明 数据范围: n, k, m <= 100
小Z的堂兄弟和小科拥有同一个爷爷（双亲的双亲)，不同的父亲（双亲结点）。
使用双亲表示法，记录下每个人的双亲。
枚举所有节点，如果其和小Z的双亲的双亲是同一人，且双亲不是同一人，那么他是小科的堂兄弟。
注意：树中堂兄的定义是，双亲在同一层（不是同一结点）的结点互为堂兄弟。
代码：
#includeusing namespace std ; const int N = 110 ; int n , m , k ; int p[N] ; int res , ps , zlayer ; int x , y ; int main () { cin >> n >> m >> k ; while (m -- ) cin >> x >> y , p[y] = x ; zlayer = 1 , ps = p[k] ; while (ps) zlayer ++ , ps = p[ps] ; for (int i = 1; i < N; i++) { int ilayer = 1 , pi = p[i] ; while (pi) ilayer ++ , pi = p[pi] ; if (ilayer == zlayer && p[i] != p[k]) res ++ ; } cout << res ; return 0 ; }
树（Tree）是n(n ≥ 0)个结点的有限集。 n == 0时称为空树。在任意一棵非空树中：
树中的元素称为：结点。
有且仅有一个称为根（Root）的结点，如图中的A结点。
当n > 1时，根以外的结点可分为m(m > 0)个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树 。
树的定义是递归的，树的子树也是一棵树，子树的子树也是一棵树。
【节点和度】
树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树（分支）数量称为结点的度。
度为0的结点称为叶子结点（Leaf）或终端结点。
度不为0的结点称为非终端结点或分支结点，除根结点以外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值。示例中图的度 = 结点A的度 = 3。
【节点之间的关系】
孩子和双亲：结点的子树的根称为该节点的孩子，该节点称为其孩子的双亲（Parent）。
兄弟：同一个双亲的孩子之间互称兄弟。
祖先：结点的祖先是从根到该结点所经分支上的所有节点（自己也是自己的祖先）。
【层次和深度】
层次：结点的层次（Level）从根开始定义，根为第1层，根的孩子为第2层，以此类推。
若某节点在第i层，则其孩子结点就在第i+1层。
双亲在同一层的结点互为堂兄弟。
树中节点的最大层次称为树的深度（Depth）或高度。
【有序树和无序树 & 森林】
如果树中节点的各子树从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林是m (m ≥0)棵互不相交的树的集合。
3.树的存储【双亲表示法】
树中除了根结点以外，每个结点都有且仅有一个双亲结点，可以用一组连续的空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。
const int N = 1010 ;
struct Tree
{
char data ;
int parent ;
} tree[N] ;
优点：对于任意结点x，可以很方便的找到其双亲结点、祖先结点和根结点（向上查找）。
缺点：对于任意结点x，如果要查找其所有的孩子结点，需要遍历所有结点。
示例：找双亲
【问题描述】输入一颗树的描述，接下来有q次询问，每次询问给定一个结点，输出其双亲结点。 输入格式： 第一行：三个整数n(n ≤ 26), m, q, 表示有n个结点， m条关系， q次询问。 接下来m行，每行两个字符x, y,表示x是y的双亲结点，数据保证合法。 接下来q行，每行一个字符x，询问x的双亲结点。 输出格式： q行，每行对应一次询问的结果。
核心代码：
struct Tree
{
char data ;
int parent ;
} tree[N] ;
int n , m , q ;
int main ()
{
cin >> n >> m >> q ;
char x , y ;
while (m -- )
{
cin >> x >> y ;
tree[y - 'A' + 1].data = y , tree[y - 'A' + 1].parent = x - 'A' + 1 ;
tree[x - 'A' + 1].data = x ;
}
while (q -- )
{
cin >> x ;
int pa = tree[x - 'A' + 1].parent ;
cout << tree[pa].data << endl ;
}
return 0 ;
}
【孩子表示法】
孩子表示法：每个结点有一个数据域，多个指针域，每个指针指向一个孩子结点。
优点：很容易找到任一结点的孩子节点。
缺点：如果要寻找某个节点的父节点，需要遍历整个存储表。
核心代码：
vector < int > tree[N] ;
int n , m , q ;
int main ()
{
cin >> n >> m >> q ;
char x , y ;
while (m -- )
{
cin >> x >> y ;
int posx = x - 'A' + 1 , posy = y - 'A' + 1 ;
tree[posx].push_back (posy) ;
}
while (q -- )
{
cin >> x ;
int posx = x - 'A' + 1 ;
sort (tree[posx].begin () , tree[posx].end ()) ;
for (int j = 0; j < tree[posx].size (); j++) cout << (char) (tree[posx][j] + 'A' - 1) << ' ' ;
puts (" ") ;
}
return 0 ;
}
3.例题
题目描述 最给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。 输入格式 第一行：n（结点个数≤100），m（边数≤200）。结点的编号是1~n 以下m行：每行两个结点x和y，表示y是x的孩子(x,y≤n)。 输出格式 第一行：树根：root； 第二行：孩子最多的结点max（如果有多个结点的孩子数量都是最多的，输出编号最小的结点）； 第三行：max的孩子（按编号由小到大输出）。 输入输出样列 输入样例1： 8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8 输出样例1： 4 2 6 7 8
使用双亲表示法，记录每个结点的双亲结点，存储完成遍历所有结点。
找树根：基于定理“一棵树中只有根节点没有双亲结点”找到根节点。
找孩子：对于任意结点i，枚举整个双亲表，所有双亲等于i的结点都是i的孩子。
通过判断孩子节点的数量，找到拥有最多孩子结点的结点maxn。
输出maxn的孩子：枚举所有结点，如果其双亲== maxn，那么该结点是maxn的孩子。
代码：
#include4.树的先序遍历(DFS遍历)using namespace std ; const int N = 110 ; int n , m , t[N] ; int x , y ; int main () { cin >> n >> m ; while (m -- ) cin >> x >> y , t[y] = x ; int maxd , id ; maxd = id = 0 ; for (int i = 1; i <= n; i++) { if (! t[i]) cout << i << endl ; int res = 0 ; for (int j = 1; j <= n; j++) if (t[j] == i) res ++ ; if (res > maxd) maxd = res , id = i ; } cout << id << endl ; for (int i = 1; i <= n; i++) { if (t[i] == id) cout << i << ' ' ; } return 0 ; }
树的遍历（traversing tree）：是指从根结点出发，按照某种次序依次访问树中所有的结点，使得每个结点被访问一次且仅被访问一次。
先序(根)遍历：若树为空，则停止遍历，否则先访问根节点，再依次先序遍历根的所有子树。
先根遍历是一种深度优先遍历(Depth-First Traversal)，简称DFS。
DFS代码：
struct Tree
{
char data ;
vector < int > childs ;
} tree[N] ;
void dfs (int r)
{
if (! r) return ;
cout << tree[r].data << ' ' ;
for (int i = 0; i < tree[r].childs.size (); i++) dfs (tree[r].childs[i]) ;
}
树的先序遍历使用分治策略，合并所有子树的遍历结果+根即是原树的遍历序列。
【示例-先序遍历】`
【问题描述】：给定一棵拥有N个节点的树 (结点编号1-N)，输出树的先序遍历序列，子树的遍历按照输入的先后顺序，先输入的先遍历，结点1为根节点。
【时间戳】
在深度优先遍历的过程中，以每个节点第一次被访问的顺序，依次给与这N个节点1~N的整数标记，该标记称为时间戳，记为dfn。
dfs遍历：
核心代码：
void dfs (int r)
{
dfn[r] = ++ cnt ;
for (int i = 0; i < T[r].size (); i++) dfs (T[r][i]) ;
}
int main ()
{
cin >> n >> m ;
int x , y ;
while (m -- ) cin >> x >> y , T[x].push_back (y) ;
dfs (1) ;
for (int i = 1; i <= n; i++) cout << dfn[i] << ' ' ;
return 0 ;
}
5.例题
题目：
小科的寻宝图2 题目描述 中奖了，中奖了，小科又中奖了，奖品为一次寻宝的机会，寻宝路线中有一个起点，多个中转站和多个终点，起点、中转站和终点位置都有一定数量的宝藏，寻宝过程中不可以走回头路且一旦到达终点寻宝就结束了。除此以外，组委会还增加了寻宝的难度，寻宝过程中不允许经过2个宝藏数量相同的站点。例如假设起点的宝藏数量为10，那么接下来小科就不可以经过宝藏也为10的其他站点了，数据保证问题一定有解。在正式寻宝之前1小时，寻宝组委会给了小科一张寻宝地图，寻宝地图中标明了起点、中转站和终点，以及每个地点的宝藏数量，由于中转站和终点实在太多了，小科无法在1个小时的时间内找出最佳路线，于是小科想请聪明的你帮助他规划出一条最佳路线，计算出他最多可以获得多少宝藏。藏宝图类似于下图，中转站有多级，和起点直接相连的为一级中转站，和一级中转站相连且不是起点的是二级中转站，和二级中转站相连且不是一级中转站的是三级中转站，以此类推。同级别的中转站之间不可通行，小科只可以从起点走向一级中转站，然后从一级到达二级以此类推，直到终点。（提示：可以将寻宝图看作一棵树）。 输入格式 第一行：一个整数n, 表示起点+中转点+终点的数量，站点编号为（1-n)，且起点的编号固定为1。(1<=n<=10000); 接下来n行，每行两个整数x, y。表示编号为x的站点拥有的宝藏数量为y。（1<=x<=n，1<= y <= 100000); 第n+2行：一个整数m, 表示路的数量(0<= m < n); 接下来m行，每行两个整数a, b；表示站点a到站点b存在一条路。 输出格式 一行：一个整数，表示小科最多可以获得的宝藏数量。 输入输出样列 输入样例1： 5 1 10 2 3 3 10 4 8 5 10 4 1 5 1 2 2 3 2 4 输出样例1： 21
思路
将藏宝图抽象为一棵树进行处理，起点是根节点，终点是叶子节点，其他都是内部结点。
问题转换：找到一条从根节点到叶结点的路径，要求路径中点的宝藏累加和最大。
同时满足：路径中任何站点所拥有的宝藏数量都不相同。问题1：如何找出所有根节点到叶节点的路径？
无论是先序遍历（DFS）还是层次遍历（BFS），都是从根节点出发，依次遍历所有结
点，每个结点都经过其双亲被访问到的，即每个节点都知道其双亲，串起来就是路径。问题2：如何确保路径中任何站点所拥有的宝藏数量都不相同？
方案1：遍历过程中，记录下路径中的所有结点，路径搜索完成后，判断是否存在冲突。
方案2：遍历过程中，使用数组标记法记录已选站点的宝藏数量，如果当前站点出现冲突，则不选择。
核心代码：
void dfs (int r , int sum)
{
if (t[r].empty ())
{
ans = max (ans , sum + money[r]) ;
return ;
}
for (int i = 0; i < t[r].size (); i++)
{
//一次先序遍历根的子树
int x = t[r][i] ;
if (! vis[money[x]])
{
vis[money[x]] = true ; //进入x站点
dfs (x , sum + money[r]) ;
vis[money[x]] = false ;
//回溯，换一个站台
}
}
}
int main ()
{
cin >> n ;
int x , y ;
while (n -- ) cin >> x >> y , money[x] = y ;
cin >> m ;
while (m -- ) cin >> x >> y , t[x].push_back (y) ;
vis[money[1]] = true ;
dfs (1 , 0) ;
cout << ans ;
return 0 ;
}
6.树的层次遍历(BFS遍历)
层次遍历：若树为空，则停止遍历。否则从树的第一层，也就是根节点开始访问，从上而下逐层访问，在同一层中，按照从左到右的顺序对节点逐个访问。
如果某个结点x先节点y被访问，则x的孩子节点也会先于y的孩子结点被访问，如果将访问本身看作进，将访问子节点看作出，则层次遍历的规则满足先进先出。
① 访问树的根结点， 访问完后，将根节点加入队列。
② 判断队列是否为空，如果不为空，则取出队首结点。
③ 依次访问队首结点的孩子结点，访问完后加入队列。
④ 重复②③，直到队列为空。
层次遍历是一种广度优先遍历(Breadth -First Traversal)，简称BFS。
BFS核心遍历：
void bfs (int r)
{
cout << tree[r].data ;
queue < int > q ;
q.push (r) ;
while (! q.empty ())
{
int v = q.front () ;
q.pop () ;
for (int i = 0; i < tree[v].childs.size (); i++)
{
int c = tree[v].childs[i] ;
cout << ' ' << tree[c].data ;
q.push (c) ;
}
}
}
【问题描述】：输入一棵树的关系描述(结点编号1-n)，输出树的层次遍历序列，任意结点的孩子节点按照从左到右的顺序输入，结点1为根节点。
qwq
题目：
题目描述 s小科的家谱中记录了n个人(n < 1000)，每个家族成员都有一个家族编号x（1 <= x <= n)，可以将小科的家谱看成一棵树，根节点的编号为1, 家谱中同辈份的家族成员，年龄大的排在左边，年龄小的排在右边，且小科家族中晚辈的年龄一定比长辈的小。输入小科的家谱，输入数据保证相同辈份的家族成员，年龄大的会先输入。请计算小科的年龄在家族中的排多少位（排位从1开始）（为方便处理，家谱中只给出了男性成员的信息） 输入格式 第一行：3个空格分隔的整数n, m和a， 其中n表示小科的家谱中的成员数量，m表示家谱树中关系的数量，a表示小科的编号。 接下来m行，每行两个空格分隔的整数x和y，表示编号为x的家族成员是编号为y的家族成员的父亲。 输出格式 一行：一个整数，表示小科的年龄在家谱树中的排行。 输入输出样列 输入样例1： 9 8 5 1 2 1 3 1 4 2 5 2 6 3 7 4 8 4 9 输出样例1： 5
年龄排序：从树根开始，从上到下从左到右的第几个就是排行第几。
样例中小科的编号是5，排行是5。
也就是层次遍历的顺序就是年龄的排行顺序，在层次遍历中，边遍历边计算遍历的顺序，遇到小科的编号则停止遍历即可。
int bfs (int r)
{
int ans = 1 ;
queue < int > q ;
q.push (r) ;
while (! q.empty ())
{
int v = q.front () ;
q.pop () ;
for (int i = 0; i < t[v].size (); i++)
{
ans ++ ;
if (t[v][i] == a) return ans ;
q.push (t[v][i]) ;
}
}
return ans ;
}
