教學目標：
1，清楚什么是樹和圖，了解基本概念，并且理解其應用場景
2，掌握一種建圖（樹）方法
3，掌握圖的dfs和樹的前中后序遍歷
例題與習題
2025NENU新生培訓（樹，圖）習題
引言
恭喜各位！當你學到圖和樹的內容的時候，已經結束了萌新的狀態。
大家想來已經早就聽過了關于樹和圖的傳說，但樹和圖到底是什么呢？又有什么用呢？
大家試想一下，我們現在已知的幾種數據結構：棧，隊列，鏈表......這些結構都有一個特點，就是線性的。
這些結構里，從前到后點與點之間的關系是1v1的，而我們不妨思考一下在如下情境中我們該如何存儲數據，我們要構造一個這樣的情景：
有許多的人，我們知道a比b年齡大，a比c大，d比c大，d比e大......該如何記錄這樣的信息呢？
如果你能獨立想明白的話，我想你已經獨立想出了算法中的一大突破，那就是樹與圖。
我們想一下應該怎么辦。是不是本能地想到應該記錄一下某個人a和所有與a有關系的人？而這顯然一個一維數組我們如果用下標來表示是誰，那么一個值通常是存不下來所有和他有關系的人的。因此我們可以用二維數組來存儲，用某一維表示a，然后另一維去存與a有關系的人。
舉個例子：
已知有三個人a， b， c， 已知a > b, b > c, a > c
我們可以用一個3 * 3 的數組來記錄它，用 1 來表示大于
? ? a? b? c
a? 0? 1? 1
b? 0? 0? 1
c? 0? 0? 0
這就是一個鄰接矩陣， 我們可以從中看出 a 比 b 大， a 比 c大， b 比 c 大
然而鄰接矩陣會用節點數目的平方的空間，因此這往往并不適用于節點數目較多而邊數較少的情況，所以我們往往會采用另一種方式鄰接表，在這種數據結構中，我們記錄和每一個頂點有關系的點。
這很方便，以上圖為例，如果我們用鄰接表的方式，我們所記錄的大概是這樣：
a ： b c
b ： c
c ：
這同樣能夠記錄圖的結構，而消耗的空間很小。
第二種方式又有兩種不同的建圖方法分別是單鏈表和動態數組，在講解建圖方式之前，我們不如先來系統地講述一下圖和樹的基本概念：
樹與圖的基本概念
一、圖 (Graph)
正如我們前面所講，圖是一種由節點（頂點）和邊組成的數據結構，通常用于表示復雜的關系。與樹不同，圖不要求有層次關系，也不一定是連通的。
1. 圖的基本概念
頂點 (Vertex)：圖中的節點。
邊 (Edge)：連接兩個頂點的線，表示它們之間的關系。
有向圖 (Directed Graph)：邊有方向，即從一個頂點指向另一個頂點。
什么樣的關系可以由有向圖表示？
無向圖 (Undirected Graph)：邊沒有方向，表示兩個頂點之間的關系是雙向的。
什么樣的關系可以由無向圖表示？
鄰接矩陣 (Adjacency Matrix)：使用二維數組表示圖的結構，適用于稠密圖。
鄰接表 (Adjacency List)：使用鏈表數組或動態數組表示圖的結構，適用于稀疏圖。
二、樹（Tree）
樹是一種特殊的圖！樹是無環的連通圖。
樹是一種分層結構的非線性數據結構，由節點和邊組成。每個樹由一個根節點和零個或多個子樹組成。
1. 樹的基本概念
節點（Node）：樹中的每個元素。
根節點（Root）：樹的最頂端節點，沒有父節點。
父節點（Parent）：一個節點的直接前驅節點。
子節點（Child）：一個節點的直接后繼節點。
葉節點（Leaf）：沒有子節點的節點。
高度（Height）：樹中節點的層次，根節點的高度為0。
深度（Depth）：節點到根節點的距離。
2. 樹的類型
二叉樹 (Binary Tree)：每個節點最多有兩個子節點，通常稱為左子節點和右子節點。
完全二叉樹：從根結點到倒數第二層滿足完美二叉樹，最后一層可以不完全填充，其葉子結點都靠左對齊。
建圖
建圖（樹），
我們接下來以這道題為例，從代碼的角度來實現一個圖的建立，樹的建立與圖完全一致
一：鄰接矩陣建圖
節點數量為n
首先創建一個n * n 的二維數組A，初始值默認為0
對每一條由u到v的邊，A[u][v] = A[v][u] = 1
二：鄰接表建圖
動態數組：
創建一個二維動態數組vector<vector<int>> B(n + 1)
對每一條由u到v的邊，B[u].push_back(v), B[v].push_back(u)
鏈表（較難）：
這種方法較難，相對來講比較傳統，大家可以自行了解
下面是這道題目的通過代碼，希望大家可以先自行嘗試解決這道問題
#include <bits/stdc++.h>using namespace std;const int N = 1010, M = 1e5 + 10;// 鄰接矩陣
int A[N][N];// 鄰接表
vector<vector<int>> B(N);int main()
{int n, m;cin >> n >> m;for (int i = 1; i <= m; i ++ ){int a, b;cin >> a >> b;// 鄰接矩陣存儲邊A[a][b] = A[b][a] = 1;// 鄰接表存儲邊B[a].push_back(b);B[b].push_back(a);}for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){cout << A[i][j] << " ";}cout << endl;}for (int i = 1; i <= n; i ++ ){// 一個點相關的邊的數量等于這個點的度數cout << B[i].size() << " ";// 題目中要求從小到大輸出sort(B[i].begin(), B[i].end());for (auto b : B[i]){cout << b << " ";}cout << endl;}return 0;
}圖（樹）的深度優先搜索
大家已經學習過在網格圖中如何進行搜索，那么在圖中該怎么進行搜索呢？我們這里僅講述dfs，bfs與其類似，大家可以課后自行嘗試
在網格圖中，我們通常使用上下左右四個方向來進行移動，但是在圖和樹中，一個點能移動到的位置是所有與其相連的點
我們用鄰接表來講的話，其dfs大概是這樣的
// 鄰接表
vector<vector<int>> B(N);// u是當前訪問的節點，fa是上一個節點
void dfs(int u, int fa)
{// b 是相連的點for (auto b : B[u]){// 如果不是父節點，就移動過去，這避免了在兩個點之間反復橫跳if (b != fa){dfs(b, u);}}
}二叉樹的前中后遍歷
在前文中，我們如果要去遍歷圖，遍歷的順序取決于給出邊的順序
舉個例子，如果給出12 13 14， 我們會先訪問2， 再訪問3，再訪問4
如果給出的是 13 12 14， 這個時候，順序就變為了3 2 4
但是在二叉樹中，我們知道一個點可以有左子節點和右子節點，如果我們按照某種順序去訪問其左子節點右子節點和其本身，那么就會得到相對來講比較特殊的遍歷順序
前序遍歷：根結點 ---> 左子樹 ---> 右子樹
中序遍歷：左子樹--->?根結點?---> 右子樹
后序遍歷：左子樹 ---> 右子樹?---> 根結點
如果課堂時間有剩余或者大家學有余力的話，我們不如一起來思考一下這些問題：
如何記錄二叉樹的左子節點和右子節點？
如果用鏈表去做的話怎么做鄰接表？
在博客開頭的情境里，能否根據已有信息排列出一個明確的年齡順序，什么情況下可以？什么情況下不行？
結語
關于樹與圖的知識還有很多，歡迎大家有不懂的知識來問學長學姐，希望大家能夠通過思考提高自己的思維能力，算法能力猛猛進步！
感謝閱讀！
)
