树的存储父子结构

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n ; //根节点数
	cin >> n ;
	//创建一个存储树结构的数组 下标表示子节点，值表示父节点
	vector<int> tree(n+1,0);//索引0不能用，初始化为0
	//读取数据
	for(int i = 0 ; i< n - 1 ; i++){
		int parent , child;
		cin >> parent >> child;
		tree[child] = parent;
	} 
	//1、寻找根节点
	int root = 0 ;
	for(int i = 1 ; i<= n ; i++){
		if(tree[i] == 0){
			root = i ;
			break;
		}
	} 
	cout << root << endl;
	
	//2、孩子最多的节点
	//2.1 统计每个节点的孩子数量
		//定义一个数组，用来存储每个节点的孩子数量
		vector<int> childCount(n+1,0);
	 	//存储父节点的孩子数量 
	 	for(int i = 1 ; i <= n ; i++){
	 		if(tree[i] !=0) childCount[tree[i]]++;
		 }
	//2.2 寻找孩子最多的节点 
		int max_node = 0 , max_count = 0;
		for(int i = 1 ; i <= n ; i++){
			if(childCount[i] > max_count){
				max_count = childCount[i];
				max_node = i ;
			}else if(childCount[i] == max_count && i < max_node){
				max_node = i ;
			}
		}
		cout << max_node << endl;
	//3、max的孩子
	//3.1 max的所有孩子
		vector<int> children;
		for(int i = 1 ; i <= n ; i ++){
			if(tree[i] == max_node) children.push_back(i);
		} 
	//3.2 将所有孩子排序
		sort(children.begin(),children.end()) ;
	//3.3 打印输出
		for(int child : children)
			cout << child << " ";	
	return 0;
}

树的高度

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 探索家族关系并记录信息
void exploreFamily(vector<vector<int>>& relations, vector<int>& parent, vector<int>& depth) {
    queue<int> familyQueue;  // 家族探索队列
    
    // 从爷爷(1)开始
    familyQueue.push(1);
    depth[1] = 1;  // 爷爷的辈分是1
    
    while (!familyQueue.empty()) {
        int current = familyQueue.front();  // 当前探索的人
        familyQueue.pop();
        
        // 检查所有和当前人有关系的人
        for (int relative : relations[current]) {
            // 如果这个人还没有被分配辈分（说明不是父母）
            if (depth[relative] == 0) {
                depth[relative] = depth[current] + 1;  // 辈分比当前人多1
                parent[relative] = current;  // 当前人是他的父亲
                familyQueue.push(relative);  // 继续探索他的家庭
            }
        }
    }
}

int main() {
    int n;  // 总人数
    cin >> n;
    
    // 准备记录本
    vector<vector<int>> relations(n+1);  // 关系网：每个人和谁有关系
    vector<int> parent(n+1, 0);         // 父节点记录本
    vector<int> depth(n+1, 0);          // 辈分记录本
    
    // 读入关系信息
    int edges = n - 1;  // 关系数量
    for (int i = 0; i < edges; i++) {
        int a, b;
        cin >> a >> b;
        
        // 记录双向关系（a认识b，b也认识a）
        relations[a].push_back(b);
        relations[b].push_back(a);
    }
    
    // 探索家族关系
    exploreFamily(relations, parent, depth);
    
    // 输出结果（从2号开始）
    for (int i = 2; i <= n; i++) {
        cout << i << " " << parent[i] << " " << depth[i] << endl;
    }
    
    return 0;
}

树的深度优先搜索

#include <iostream>
#include <vector>
using namespace std;

// 深度优先遍历方法
void dfs_traversal(vector<vector<int>>& children, int current, vector<int>& result) {
    // 1. 访问当前节点（记录到结果中）
    result.push_back(current);
    
    // 2. 按顺序探索所有孩子（树枝）
    for (int kid : children[current]) {
        // 3. 递归探索每个子树
        dfs_traversal(children, kid, result);
    }
}

int main() {
    int n;  // 总节点数
    cin >> n;
    
    // 创建树结构：存储每个节点的孩子
    vector<vector<int>> children(n+1);  // 0号位置不用，从1开始
    
    // 读入父子关系
    for (int i = 0; i < n-1; i++) {
        int father, child;
        cin >> father >> child;
        children[father].push_back(child); // 把孩子加入父亲的列表
    }
    
    vector<int> result; // 存储遍历结果
    
    // 调用DFS方法进行遍历（从根节点1开始）
    dfs_traversal(children, 1, result);
    
    // 输出结果（注意空格格式）
    for (int i = 0; i < result.size(); i++) {
        if (i == 0) {
            cout << result[i]; // 第一个不加空格
        } else {
            cout << " " << result[i]; // 后面加空格
        }
    }
    
    return 0;
}

树的广度优先搜索

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 广度优先遍历方法
vector<int> bfs_traversal(vector<vector<int>>& family, int start) {
    vector<int> result;  // 存储遍历结果
    queue<int> line;     // 排队队列
    
    line.push(start);    // 从起点开始排队
    
    while (!line.empty()) {
        int current = line.front(); // 当前点到的人
        line.pop();                 // 点完名离开队列
        
        result.push_back(current);  // 记录当前人
        
        // 让当前人的所有孩子加入队列
        for (int kid : family[current]) {
            line.push(kid);
        }
    }
    
    return result;
}

int main() {
    int n;  // 总人数
    cin >> n;
    
    // 创建家谱图：每个父亲的孩子列表
    vector<vector<int>> family(n+1);  // 0号位置不用，从1开始
    
    // 读入父子关系
    for (int i = 0; i < n-1; i++) {
        int father, child;
        cin >> father >> child;
        family[father].push_back(child); // 把孩子加入父亲的家谱
    }
    
    // 调用BFS方法进行遍历
    vector<int> sequence = bfs_traversal(family, 1);
    
    // 输出结果（注意空格格式）
    for (int i = 0; i < sequence.size(); i++) {
        if (i == 0) {
            cout << sequence[i]; // 第一个不加空格
        } else {
            cout << " " << sequence[i]; // 后面加空格
        }
    }
    
    return 0;
}