第1课：树的概念
进度 0/24
🌳
树的概念
从一条链到一棵树，数据开始分叉生长！
📖知识引入
🌳树是什么
由节点和边组成的层次结构，像一棵倒着生长的树，根在上、叶在下
👨👧父与子
直接相连的上下级节点，一个父亲可以有多个孩子，一个孩子只有一个父亲
🍃叶子节点
没有孩子的节点，长在树的末梢，是这条分支的终点
📏深度与高度
从根走到某节点经过的边数叫深度，根的深度为0，往下逐层加一
💡
树是n个节点的有限集合，有且仅有一个根，并且绝不能出现环——一旦连成环它就不再是树了
🔍用fa数组存一棵树
#include <iostream>
using namespace std;
int fa[105]; // fa[x] 存 x 的父节点编号
int main() {
int n = 6; // 6 个节点，1 号是根
fa[1] = 0; // 根节点没有父亲
fa[2] = 1; fa[3] = 1; // 1 号的孩子是 2、3
fa[4] = 2; fa[5] = 2; fa[6] = 3;
// 沿 fa 一路向上，求 6 号节点的深度
int x = 6, depth = 0;
while (fa[x] != 0) { x = fa[x]; depth++; }
cout << "深度=" << depth << endl; // 输出 2
return 0;
}fa[x]存x的父节点，沿fa一路向上就能求出任何节点的深度。
🎯小测验
第1题：树中可以出现环吗？
第2题：一棵树有几个根节点？
第3题：叶子节点的特点是什么？
📝本课知识点
- ✓树=节点+边，无环且连通
- ✓有且仅有一个根节点
- ✓没有孩子的节点叫叶子
第1课完成！继续探索下一课吧 🚀