南通网站排名公司,wordpress app源码,网络推广有前途吗,cms仿站教程一、树的定义
树的定义 树型结构是⼀类重要的⾮线性数据结构。 • 有⼀个特殊的结点#xff0c;称为根结点#xff0c;根结点没有前驱结点。 • 除根结点外#xff0c;其余结点被分成M个互不相交的集合T1 、T2 、...、Tm T#xff0c;其中每⼀个集合⼜是⼀棵树#xff0c…一、树的定义
树的定义 树型结构是⼀类重要的⾮线性数据结构。 • 有⼀个特殊的结点称为根结点根结点没有前驱结点。 • 除根结点外其余结点被分成M个互不相交的集合T1 、T2 、...、Tm T其中每⼀个集合⼜是⼀棵树称这棵树为根节点的⼦树。 因此树是递归定义的。
树的基本术语 • 结点的度树中⼀个结点孩⼦的个数称为该结点的度。 • 树的度树中结点最⼤的度数称为树的度。 • 树的⾼度深度树中结点的最⼤层数称为树的⾼度深度。 • 路径树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的路径⻓度为序列中边的个数。
有序树和⽆序树 • 有序树结点的⼦树按照从左往右的顺序排列不能更改。 • ⽆序树结点的⼦树之间没有顺序随意更改。 这个认知会在我们后续学习⼆叉树的时候⽤到因为⼆叉树需要区分左右孩⼦。
有根树和⽆根树 • 有根树树的根节点已知是固定的。 • ⽆根树树的根节点未知谁都可以是根结点。 这个认知主要会影响我们对于树的存储。在存储树结构的时候我们最重要的就是要存下逻辑关系。如果是⽆根树⽗⼦关系不明确此时我们需要把所有的情况都存下来。⽐如a和b之间有⼀条边我们不仅要存a有⼀个孩⼦b也要存b有⼀个孩⼦a。 甚⾄有的时候在有根树的题⽬⾥也要这样存储。
二、树的存储
孩⼦表⽰法
孩⼦表⽰法是将每个结点的孩⼦信息存储下来。 如果是在⽆根树中⽗⼦关系不明确我们会将与该结点相连的所有的点都存储下来。
实现⽅式⼀vector数组实现
案例 题⽬描述 给定⼀棵树该树⼀共有n 个结点编号分别是1 ∼ n 。 输⼊描述 第⼀⾏⼀个整数n 表⽰n 个结点。 接下来n − 1 ⾏每⾏两个整数u, v 表⽰u 和v 之间有⼀条边。vector是可变⻓数组如果只涉及尾插效率还是可以的。⽽树结构这种⼀对多的关系正好可以利⽤尾插把所有的关系全部存起来。 • 因此可以创建⼀个⼤⼩为n 1 的vector 数组edges[n 1] 。 • 其中edges[i] ⾥⾯就保存着i 号结点所连接的结点。
#include iostream
#include vector
using namespace std;
const int N 1e5 10;
int n;
vectorint edges[N]; // 存储树
int main()
{cin n;for(int i 1; i n; i){int a, b; cin a b;// a 和 b 之间有⼀条边 edges[a].push_back(b);edges[b].push_back(a);}return 0;
}
实现⽅式⼆链式前向星
链式前向星的本质就是⽤数组来模拟链表。
#include iostream
using namespace std;
const int N 1e5 10;
// 链式前向星
int h[N], e[N * 2], ne[N * 2], id;
int n;
// 其实就是把 b 头插到 a 所在的链表后⾯
void add(int a, int b)
{id;e[id] b;ne[id] h[a];h[a] id;
}
int main()
{cin n;for(int i 1; i n; i){int a, b; cin a b;// a 和 b 之间有⼀条边 add(a, b); add(b, a);}return 0;
}
三、树的遍历
树的遍历就是不重不漏的将树中所有的点都扫描⼀遍。 在之前学过的线性结构中遍历就很容易直接从前往后扫描⼀遍即可。但是在树形结构中如不 按照⼀定的规则遍历就会漏掉或者重复遍历⼀些结点。因此在树形结构中要按照⼀定规则去遍历。常⽤的遍历⽅式有两种⼀种是深度优先遍历另⼀种是宽度优先遍历。
深度优先遍历-DFS ⽤ppt展⽰效果更佳 深度优先遍历英⽂缩写为DFS全称是DepthFirstSearch中⽂名是深度优先搜索是⼀种⽤于遍历或搜索树或图的算法。所谓深度优先就是说每次都尝试向更深的节点⾛也就是⼀条路⾛到⿊。 具体流程 1. 从根节点出发依次遍历每⼀棵⼦树 2. 遍历⼦树的时候重复第⼀步。 因此深度优先遍历是⼀种递归形式的遍历可以⽤递归来实现。
案例 题⽬描述 给定⼀棵树该树⼀共有n 个结点编号分别是1~n 。 输⼊描述 第⼀⾏⼀个整数n 表⽰n 个结点。 接下来n − 1 ⾏每⾏两个整数u, v 表⽰u 和v 之间有⼀条边。
1、⽤vector数组存储
注存储树结构的时候会把相邻的所有结点都存下来这样在扫描⼦树的时候会直接扫描到上⼀ 层这不是我们想要的结果。 因此需要⼀个st 数组来标记哪些结点已经访问过接下来dfs 的时候就不去遍历那些点
int n;
vectorint edges[N]; // edges[i] 保存着 i 号结点相连的所有点
bool st[N]; // 标记当前结点是否已经被遍历过
// 当前遍历到 u 这棵⼦树
void dfs1(int u)
{// 先访问该点 cout u ;st[u] true; // 标记该点已经被访问过 // 访问它的⼦树 for(auto v : edges[u]){if(!st[v]) dfs1(v); // 如果没有遍历过再去遍历 }
}
// ⽤ vector 数组
void test1()
{cin n;for(int i 1; i n - 1; i){int a, b; cin a b; // 读⼊⼀条边 edges[a].push_back(b); // 保存 a - b 的⼀条边 edges[b].push_back(a); // 保存 b - a 的⼀条边 }dfs1(1);
}
2、链式向前星存储
int n;
int h[N], e[N * 2], ne[N * 2], id;
bool st[N]; // 标记当前结点是否已经被遍历过
void add(int a, int b)
{id;e[id] b; // 搞⼀个格⼦存 b // 把 b 头插在 a 这个链表的后⾯ ne[id] h[a];h[a] id;
}
// 当前遍历到 u 这棵⼦树
void dfs2(int u)
{cout u ;st[u] true;for(int i h[u]; i; i ne[i]){int v e[i];if(!st[v]) dfs2(v);}
}
// ⽤数组模拟链表
void test2()
{cin n;for(int i 1; i n - 1; i){int a, b; cin a b;add(a, b); add(b, a);}dfs2(1);
}
宽度优先遍历-BFS
宽度优先遍历英⽂缩写为BFS全称是BreadthFirstSearch也叫⼴度优先遍历。也是⼀种⽤于遍历或搜索树或图的算法。所谓宽度优先。就是每次都尝试访问同⼀层的节点。如果同⼀层都访问完了再访问下⼀层。 算法过程可以看做是在树和图中在起点放上⼀个细菌每秒向周围的那些⼲净的位置扩散⼀层直到把所有位置都感染。
具体实现⽅式借助队列。 1. 初始化⼀个队列 2. 根节点⼊队同时标记该节点已经⼊队 3. 当队列不为空时拿出队头元素访问然后将队头元素的所有孩⼦⼊队同时打上标记 4. 重复3 过程直到队列为空。
用vector实现
int n;
vectorint edges[N]; // edges[i] 保存着 i 号结点相连的所有点
bool st[N]; // 标记哪些点已经⼊过队了
void bfs1()
{queueint q;q.push(1);st[1] true;while(q.size()){auto u q.front(); q.pop();cout u ;// 让孩⼦⼊队 for(auto v : edges[u])//把这点的孩子全部加入进来{if(!st[v]){q.push(v);st[v] true;}}}
}
// ⽤ vector 数组
void test1()
{cin n;for(int i 1; i n - 1; i){int a, b; cin a b; // 读⼊⼀条边 edges[a].push_back(b); // 保存 a - b 的⼀条边 edges[b].push_back(a); // 保存 b - a 的⼀条边 }bfs1();
}
链式向前星存储
int n;
int h[N], e[N * 2], ne[N * 2], id;
bool st[N]; // 标记哪些点已经⼊过队了
void add(int a, int b)
{id;e[id] b; // 搞⼀个格⼦存 b // 把 b 头插在 a 这个链表的后⾯ ne[id] h[a];h[a] id;
}
void bfs2()
{queueint q;q.push(1);st[1] true;while(q.size()){auto u q.front(); q.pop();cout u ;for(int i h[u]; i; i ne[i]){int v e[i];if(!st[v]){q.push(v);st[v] true;}}}
}
// ⽤数组模拟链表
void test2()
{cin n;for(int i 1; i n - 1; i){int a, b; cin a b;add(a, b); add(b, a);}bfs2();
}
