官渡网站建设淘客怎么做推广网站

官渡网站建设,淘客怎么做推广网站,建设银行网站修改手机号,做地产设计的公司树是一个对于我这种小白来说是接触的第一个较复杂的数据结构#xff0c;不像之前的线性结构#xff0c;树让人感觉是从一个线到面的进阶。树的定义是由一个根节点和许多子节点组成#xff0c;再由子节点成为新的根节点有点像递归的过程#xff0c;因此树的许多操作都要有递…树是一个对于我这种小白来说是接触的第一个较复杂的数据结构不像之前的线性结构树让人感觉是从一个线到面的进阶。树的定义是由一个根节点和许多子节点组成再由子节点成为新的根节点有点像递归的过程因此树的许多操作都要有递归的参与。树的基本术语节点的度树中的节点的子节点的个数称为度。树的度树中节点最大的度。树的高度树的层数或者深度。路径两个子结点之间的距离。树又分为有根树和无根树无序树指的是树的根是变化的根节点可以是子节点子节点可以是根节点。有根树的根节点是固定的。树又分为有序树和无序树有序树中树的子节点不可变化无序树反之。树的储存是一个相较于线性结构完全不同的由于一对多的特性使得他的存储变得困难。当我们在处理无根树时由于根的不确定性所以应在每个节点相互存储两次。对此我们有两种存储方式vector数组和链式前向星。vector数组是将以根节点为数组名的数组中存储他的子节点。#include iostream #include vector using namespace std; const int N 1e5 10; int n;//节点的个数 vectorintedges[N]; int main() { cin n; for(int i 1; i n; i) { int u, v; cin u v; edges[u].push_back(v); edges[v].push_back(u);//由于没有固定的根节点需要相互储存 } return 0; }链式前向向星指的是用链表进行存储。#include iostream using namespace std; const int N 1e5 10; int h[N], e[2 * N], ne[2 * N]; int n, id; void add(int a, int b) { id; e[id] b; ne[id] h[a]; h[a] id; } int main() { cin n; for(int i; i n; i) { int a, b; cin a b; add(a,b); add(b,a);//要将两种根的情况存储 } return 0; }树的遍历如果按照之前的方法随便遍历的话很容易漏掉数据。因此树有它特有的两种遍历方式深度优先遍历DFS和宽度优先遍历BFS。深度优先遍历是由根节点为起点一直往子节点的子节点不断遍历直到找到叶子节点没有子节点时原路返回至其他子节点再进行遍历直到将所有数据遍历完结束。#include iostream #include vector using namespace std; const int N 1e6 10; vectorintedges[N]; int n; bool st[N];//由于根节点不知要将历遍过的节点标记防止死循环 void dfs(int u)//以它为根节点的往后的子节点 { cout u ; st[u] true; for(auto v : edges[u]) { if(!st[v]) { dfs(v); } } } int main() { int n; cin n; for(int i 1; i n; i) { int u, v; cin u v; edges[u].push_back(v); edges[v].push_back(u); } dfs(1);//以1为根结点的树 }上述使用的是vector数组储存的树的深度优先遍历接下来使用链式前向星再来模拟一次。要点由于根节点的未知要使用额外的bool 数组来标记已历遍过的数据。#include iostream using namespace std; const int N 1e6 10; int h[N], e[N * 2], ne[N * 2]; int id, n; bool st[N]; void add(int a,int b) { id; e[id] b; ne[id] h[a]; h[a] id; } int dfs(int u) { cout u ; st[u] true; for(int i h[a]; i ne[id]) { int v e[i]; if(!st[v]) { dfs(v); } } } int main() { cin n; for(int i 1; i n; i) { int a, b; cin a b; add(a,b); add(b,a); } dfs(1); }现在介绍宽度优先遍历也叫广度优先遍历指的是将同一层的节点遍历完后再遍历下一层。所以根据队列的特性我们可以应用queue来完成这个遍历。我们还是先用vector数组的存储方法来模拟不要忘了将已遍历过了的点标记 与之前相同#include iostream #include vector #include queue using namespace std; const int N 1e6 10; vectorintedges[N]; int n; bool st[N]; void bfs() { queueintq; q.push(1); while (q.size()) { int u q.front(); q.pop(); cout u ; for (auto v : edges[u]) { if (!st[v]) { q.push(v); st[v] true; } } } } int main() { cin n; for (int i 1; i n; i) { int u, v; edges[u].push_back(v); edges[v].push_back(u); } bfs(); }再来使用链式前向星来储存时的bfs#include iostream #include queue using namespace std; const int N 1e6 10; int h[N], e[N * 2], ne[N * 2]; int n, id; bool st[N]; void add(int a, int b) { id; e[id] b; ne[id] h[a]; h[a] id; } void bfs() { queueintq; q.push(1); while (q.size()) { int 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; } } } } int main() { cin n; for (int i 1; i n; i) { int a, b; cin a b; add(a, b); add(b, a); } bfs(); }#include iostream #include queue using namespace std; const int N 1e6 10; int h[N], e[N * 2], ne[N * 2]; int n, id; bool st[N]; void add(int a, int b) { id; e[id] b; ne[id] h[a]; h[a] id; } void bfs() { queueintq; q.push(1); while (q.size()) { int 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; } } } } int main() { cin n; for (int i 1; i n; i) { int a, b; cin a b; add(a, b); add(b, a); } bfs(); }树的种类还有许多可分为N叉树我认为树的进阶和之后的节点的捆绑就是类似图的数据结构吧当然纯属个人想法等到学到该内容再与大家讨论。