东莞 企业网站建设电脑浏览器打不开网页

当前位置： 首页 > news >正文

东莞 企业网站建设,电脑浏览器打不开网页,辽宁建设工程网,漳州网站建设网站制作树形结构不仅能表示数据间的指向关系#xff0c;还能表示出数据的层次关系#xff0c;而有很明显的递归性质。因此#xff0c;我们可以利用树的性质解决更多种类的问题。 但是在平常的使用中#xff0c;我们并不需要使用这么复杂的结构#xff0c;只需要建立一个包含int r… 树形结构不仅能表示数据间的指向关系还能表示出数据的层次关系而有很明显的递归性质。因此我们可以利用树的性质解决更多种类的问题。 但是在平常的使用中我们并不需要使用这么复杂的结构只需要建立一个包含int right和int left的结构体即可left和right用于指示该节点的左儿子和右儿子。 一、【P4913】二叉树深度递归/层次遍历 本题的重点在于二叉树的存储和二叉树的层次遍历。 1. 二叉树存储考虑一个二叉树的每个节点都有两个子节点所以我们可以考虑用一个结构体来存储。其中left和right分别代表节点的左节点编号和右节点编号。 struct node {int left, right; }; node tree[MAXN];

1. 二叉树层次遍历我们可以从根节点出发先递归遍历该节点的左节点再递归遍历该节点的右节点。对于每个父亲节点先比较左右子树的高度然后选取较高的子树将其深度加1每次遍历更新子树的高度。当遍历到叶子节点后返回0叶子节点的左右子树高度均为0。 int maxDepth(int id) {if (id 0) return 0;return 1 max(maxDepth(Tree[id].left), maxDepth(Tree[id].right)); } AC代码 #include iostream #include string #include algorithm #include cmathusing namespace std;struct node {int left;int right; }Tree[1000005];int maxDepth(int id) {if (id 0) return 0;return 1 max(maxDepth(Tree[id].left), maxDepth(Tree[id].right)); }int main() {int n; cin n;for (int i 1; i n; i){int a, b; cin a b;Tree[i].left a;Tree[i].right b;}cout maxDepth(1);} 二、【P1827】美国血统前中后序遍历 前序遍历、中序遍历和后序遍历是三种利用深度优先搜索遍历二叉树的方式。它们是在对节点访问的顺序有一点不同其它完全相同。 需要注意的是下图中伪代码并未给出base case即递归返回的条件。 AC代码 先序遍历的特点是优先遍历根节点所以整棵树的根应该会在inorder字符串的最开始出现中序遍历的特点是优先遍历左子树然后遍历根节点所以我们可以根据中序遍历序列判断左右子树中包含哪些点。 以本题为例 中序inorder遍历ABEDFCHG先序preorder遍历CBADEFGH。 首先可以根据preorder判断C为根节点然后依据inorder判断ABEDF为左子树中的节点HG为右子树中的节点。回到preorder序列第二个节点是B所以左子树的根节点为B依据inorder序列可知A构成次级左子树DEF构成次级右子树。回到preorder序列第三个节点是A刚好是以B为根的子树的左子树的根第四个节点是D所以以B为根的子树的右子树的根为D。以此类推可以还原整棵树的情况。 #include iostream #include string #include algorithm #include cmath #include vector #include map #include stack #include setusing namespace std;struct TreeNode //建树 {char val;TreeNode* left;TreeNode* right;TreeNode() :val(0), left(nullptr), right(nullptr) {}TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}TreeNode(char x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} };//对preorder中的[s0,e0]部分操作s1用于跟踪preorder序列中某个父亲节点 TreeNode* buildTree(string preorder, mapchar, int mp, int s0, int e0, int s1) {if (s0 e0) return nullptr;char mid preorder[s1];int index mp[mid]; //找到当前父亲节点在中序遍历inorder中的位置int left_length index - s0; //左子树大小TreeNode* node new TreeNode(mid);node-left buildTree(preorder, mp, s0, index - 1, s1 1);node-right buildTree(preorder, mp, index 1, e0, s1 1 left_length);return node; }void PostOrder(TreeNode* tree) {if (!tree) return;PostOrder(tree-left);PostOrder(tree-right);cout tree-val; }int main() {string preorder, inorder;cin inorder preorder;mapchar, int mp;//使用map存储便于搜索for (int i 0; i inorder.length(); i)mp[inorder[i]] i;TreeNode* res buildTree(preorder, mp, 0, inorder.length() - 1, 0);PostOrder(res); } 由于需要通过preorder序列的节点查询该点在inorder序列的位置所以将inorder序列用map存储实现O(1)量级的查询。 使用buildTree函数递归还原整棵树然后使用postorder函数对树进行后序遍历得到答案。 三、【P1229】遍历问题前中后序遍历 思路给定inorder能确定树的具体结构是因为可以确定子树是左子树还是右子树而只给定preorder和postorder则不能确定这就是会出现不同树结构的原因。 只有前和后那么主要问题就是没有办法处理只有一个子树的情况因为这种情况下不知道子树究竟是这个节点的左子树还是右子树也就是说其实这道题要判断遍历中存在着多少个只有一棵子树的情况。对于前如果一个结点的下个结点等于后中对应结点的前一个结点的话那么这个结点就是根节点且其只有一个子树。sum初始化为1出现一个只有一棵子树的情况就把sum*2每次会出现两种不同的情况分别是出现左子树和出现右子树。 AC代码 #include iostream #include string #include algorithm #include cmath #include vector #include map #include cstring #include queueusing namespace std; const int INF 0x7fffffff;int main() {string preorder, postorder;cin preorder postorder;int sum 1;for (int i 0; i preorder.length() - 2; i){for (int j 0; j postorder.length() - 1; j){if (preorder[i] postorder[j] preorder[i 1] postorder[j - 1]){sum * 2;}}}cout sum endl; } 四、【P1030】求先序序列前中后序遍历 首先一点基本常识给你一个后序遍历那么最后一个就是根如ABCD则根为D因为题目求先序意味着要不断找根。 那么我们来看这道题方法示例 中序ACGDBHZKX后序CDGAHXKZB首先可找到主根B 那么我们找到中序遍历中的B由这种遍历的性质可将中序遍历分为ACGD和HZKX两棵子树那么对应可找到后序遍历CDGA和HXKZ从头找即可从而问题就变成求 中序遍历ACGD后序遍历CDGA的树中序遍历HZKX后序遍历HXKZ的树 接着递归按照原先方法找到 1.子根A再分为两棵子树 2.子根Z再分为两棵子树。 就按这样一直做下去先输出根再递归。 模板概括为 step1:找到根并输出step2:将中序后序各分为左右两棵子树step3:递归重复step1,2 AC代码 #include iostream #include string #include algorithm #include cmath #include vector #include map #include cstring #include queueusing namespace std; const int INF 0x7fffffff;string inorder, postorder;void preorder(string in,string after) {if (in.size() 0){char ch after[after.size() - 1];cout ch;int k in.find(ch);preorder(in.substr(0, k), after.substr(0, k)); //左子树preorder(in.substr(k 1), after.substr(k, in.size() - k - 1));//从k开始截取这么多个数} }int main() {cin inorder postorder;preorder(inorder, postorder); } 将234三题进行比较2的解题思路具有普适性但是建树的过程相对复杂4的解题思路较为清晰但是缺点在于只能输出序列并不能得到完整的树。 五、【P5076】简化二叉树二叉搜索树 参考https://www.cnblogs.com/do-while-true/p/13566274.html  但值得强调的是二叉搜索树是一种低级的平衡二叉树因为在最差情况下可以会呈现链状结构导致时间复杂度为O(n)而不是所需的O(logN)。因此只需要了解即可重点需要掌握的是平衡二叉树。 splay搜索树的几种操作 1插入x 是当前节点的下标v 是要插入的值。要在树上插入一个 v 的值就要找到一个合适 v 的位置如果本身树的节点内有代表 v 的值的节点就把该节点的计数器加 11 否则一直向下寻找直到找到叶子节点这个时候就可以从这个叶子节点连出一个儿子代表 v 的节点。具体向下寻找该走左儿子还是右儿子是根据二叉搜索树的性质来的。 void add(int x,int v) {tree[x].siz;//如果查到这个节点说明这个节点的子树里面肯定是有v的所以sizif(tree[x].valv){//如果恰好有重复的数就把cnt退出即可因为我们要满足第四条性质tree[x].cnt;return ;}if(tree[x].valv){//如果vtree[x].val说明v实在x的左子树里if(tree[x].ls!0)add(tree[x].ls,v);//如果x有左子树就去x的左子树else{//如果不是v就是x的左子树的权值cont;//cont是目前BST一共有几个节点tree[cont].valv;tree[cont].siztree[cont].cnt1;tree[x].lscont;}}else{//右子树同理if(tree[x].rs!0)add(tree[x].rs,v);else{cont;tree[cont].valv;tree[cont].siztree[cont].cnt1;tree[x].rscont;}} } 2找前驱x 是当前的节点的下标val 是要找前驱的值ans 是目前找到的比 val 小的数的最大值。找前驱的方法也是不断的在树上向下爬找具体节点具体爬的方法可以参考代码注释部分。 int queryfr(int x, int val, int ans) {if (tree[x].valval){//如果当前值大于val就说明查的数大了所以要往左子树找if (tree[x].ls0)//如果没有左子树就直接返回找到的ansreturn ans;else//如果不是的话去查左子树return queryfr(tree[x].ls,val,ans);}else{//如果当前值小于val就说明我们找比val小的了if (tree[x].rs0)//如果没有右孩子就返回tree[x].val因为走到这一步时我们后找到的一定比先找到的大(参考第二条性质)return (tree[x].valval) ? tree[x].val : ans//如果有右孩子我们还要找这个节点的右子树因为万一右子树有比当前节点还大并且小于要找的val的话ans需要更新if (tree[x].cnt!0)//如果当前节数的个数不为0ans就可以更新为tree[x].valreturn queryfr(tree[x].rs,val,tree[x].val);else//反之ans不需要更新return queryfr(tree[x].rs,val,ans);} } 3找后继与找前驱同理只不过需要反过来。 int queryne(int x, int val, int ans) {if (tree[x].valval){if (tree[x].rs0)return ans;elsereturn queryne(tree[x].rs,val,ans);}else{if (tree[x].ls0)return (tree[x].valval)? tree[x].val : ans;if (tree[x].cnt!0)return queryne(tree[x].ls,val,tree[x].val);elsereturn queryne(tree[x].ls,val,ans);} } 4按值找排名这里我们就要用到 siz 了排名就是比这个值要小的数的个数再 1所以我们按值找排名就可以看做找比这个值小的数的个数最后加上 1 即可。 int queryval(int x,int val) {if(x0) return 0;//没有排名 if(valtree[x].val) return tree[tree[x].ls].siz;//如果当前节点值val则我们加上现在比val小的数的个数也就是它左子树的大小 if(valtree[x].val) return queryval(tree[x].ls,val);//如果当前节点值比val大了我们就去它的左子树找val因为左子树的节点值一定是小的 return queryval(tree[x].rs,val)tree[tree[x].ls].siztree[x].cnt;//如果当前节点值比val小了我们就去它的右子树找val同时加上左子树的大小和这个节点的值出现次数 //因为这个节点的值小于val这个节点的左子树的各个节点的值一定也小于val } //注:这里最终返回的是排名-1也就是比val小的数的个数在输出的时候记得1 5按排名找值排名为 n 的数在BST上是第 n 靠左的数。或者说排名为 n 的数的节点在BST中它的左子树的 siz 与它的各个祖先的左子树的 siz 相加恰好 n (这里相加是要减去重复部分)。 int queryrk(int x,int rk) {if(x0) return INF; if(tree[tree[x].ls].sizrk)//如果左子树大小rk了就说明答案在左子树里 return queryrk(tree[x].ls,rk);//查左子树 if(tree[tree[x].ls].siztree[x].cntrk)//如果左子树大小加上当前的数的多少恰好k说明我们找到答案了 return tree[x].val;//直接返回权值 return queryrk(tree[x].rs,rk-tree[tree[x].ls].siz-tree[x].cnt);//否则就查右子树同时减去当前节点的次数与左子树的大小 } AC代码 #include iostream #include string #include algorithm #include cmath #include vector #include map #include stack #include setusing namespace std; const int INF 0x7fffffff;struct node {int val; //节点值int left, right; //左右子树int cnt; //计数器int siz; //子树大小 }tree[100005]; int cont 0;//记录节点数量//初始化 void init() {for (int i 0; i 100005; i){tree[i].val 0;tree[i].left 0;tree[i].right 0;tree[i].cnt 0;tree[i].siz 0;} }//添加新点 void add(int x, int value) //当前节点为x需要插入value {tree[x].siz; //肯定在x子树上规模加一if (tree[x].val value) //如果value刚好等于节点值计数器加一即可{tree[x].cnt;return;}if (tree[x].val value) //如果x的值大于valuevalue只能放在x的左子树上{if (tree[x].left ! 0)//如果左子树上有节点递归查找add(tree[x].left, value);else//如果左子树上没有点直接添加{cont;tree[cont].val value;tree[cont].siz tree[cont].cnt 1;tree[x].left cont;}}else if (tree[x].val value)//如果x的值小于valuevalue要放到x的右子树上{if (tree[x].right ! 0)//如果右子树上有节点递归查找add(tree[x].right, value);else//如果右子树上没有点直接添加{cont;tree[cont].val value;tree[cont].siz tree[cont].cnt 1;tree[x].right cont;}} }//查找前驱 int query_front(int x, int value, int ans) //x 是当前的节点的下标val 是要找前驱的值ans 是目前找到的比val小的数的最大值。 {if (cont 0) return -INF;if (tree[x].val value)//当前节点val大于所查value到左子树查找{if (tree[x].left 0) //左子树不存在那么前驱为ansreturn ans;elsereturn query_front(tree[x].left, value, ans); //否则遍历左子树}else{if (tree[x].right 0)//若无右孩子说明当前点满足条件return (tree[x].val value) ? tree[x].val : ans;else{if (tree[x].cnt ! 0) //如果当前节点的个数不为0ans就可以更新为tree[x].valreturn query_front(tree[x].right, value, tree[x].val);elsereturn query_front(tree[x].right, value, ans);}} }//查找后继 int query_next(int x, int value, int ans) {if (cont 0) return INF;if (tree[x].val value){if (tree[x].right 0)return ans;elsereturn query_next(tree[x].right, value, ans);}else{if (tree[x].left 0)return (tree[x].val value) ? tree[x].val : ans;else{if (tree[x].cnt ! 0)return query_next(tree[x].left, value, tree[x].val);elsereturn query_next(tree[x].left, value, ans);}} }//按值找排名 int val_to_rank(int x, int value) {if (x 0) return 0;if (value tree[x].val)return tree[tree[x].left].siz;//比它小的数if (value tree[x].val)return val_to_rank(tree[x].left, value);if (value tree[x].val)return val_to_rank(tree[x].right, value) tree[tree[x].left].siz tree[x].cnt;//左子树上的所有点加上根上的点都小于value }//按排名找值 int rank_to_val(int x, int rank) {if (x 0)return INF;if (tree[tree[x].left].siz rank) //如果小于x.val的数多于rank那么该值一定在左子树上递归查找return rank_to_val(tree[x].left, rank);if (tree[tree[x].left].siz tree[x].cnt rank) //如果左子树上的点数根上的节点数大于rank且左子树上的点数小于rank那么点x的值为所需值return tree[x].val;return rank_to_val(tree[x].right, rank - tree[tree[x].left].siz - tree[x].cnt); //否则在右子树上要先将左子树根上的点数减去 }int main() {int q; cin q;init();for (int i 1; i q; i){int op, v;cin op v;if (op 1)cout val_to_rank(1, v) 1 endl;else if (op 2)cout rank_to_val(1, v) endl;else if (op 3)cout query_front(1, v, -INF) endl;else if (op 4)cout query_next(1, v, INF) endl;else{if (cont 0){cont;tree[cont].cnt tree[cont].siz 1;tree[cont].val v;}elseadd(1, v);}} } 六、【P1364】医院设置BFS广搜 广度优先搜索breadth-first search BFS不同与深度优先搜索它是一层层进行遍历的因此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历广度优先搜索时按照“广”的方向进行遍历的也常常用来处理最短路径等问题。 在本题中由于每个点都可以是原点树根因此采用树结构存储是行不通的因为指针只能单方向指向。这里采用邻接矩阵的方式来存储树。 AC代码 本题中只考虑每个点到根节点的距离因此采用DFS和BFS均可。 由于BFS操作起来更直观因此本题用普通图的形式存储树枚举每个节点为根节点的情况进行n遍BFS然后每遍都进行答案的比较更新。 #include iostream #include string #include algorithm #include cmath #include vector #include map #include cstring #include queueusing namespace std; const int INF 0x7fffffff;bool graph[105][105] { 0 }; bool visit[105] { 0 }; int value[105] { 0 };struct node {int num;int step; //用于存储某点到根节点的距离 }; int n;int BFS(int x) //以x为根对树进行BFS遍历 {memset(visit, 0, sizeof(visit)); queuenode q;visit[x] 1;node gen; gen.num x, gen.step 0;q.push(gen); //将树根节点入队int sum 0;while (!q.empty()){node now q.front();q.pop();for (int i 1; i n; i) //依次取出队列中的点并找到与该点距离为1且未被访问过的点{if (graph[now.num][i] !visit[i]){node next;next.num i, next.step now.step 1; //更新选中点到根的距离visit[i] 1;q.push(next);sum value[i] * next.step; //该点的权重乘以与根的距离}}}return sum; }int main() {cin n;for (int i 1; i n; i){int w, u, v;cin w u v;value[i] w;if (u ! 0)graph[i][u] graph[u][i] 1;if (v ! 0)graph[i][v] graph[v][i] 1;}int MinDis INF;for (int i 1; i n; i){int tmp BFS(i);if (tmp MinDis)MinDis tmp;}cout MinDis endl; }由于bfs每遍都是O(VE)的而这里特殊之处在于本身是个树所以是n个节点和n-1条边 所以总复杂度近似为. 七、【P3884】二叉树问题Floyd算法 树其实一种特殊的图。 即没有环路一定联通而且有且有只有一个节点没有入度的图。 树上任意两点间的距离可以直接通过最短路算法获得。树的深度就是距离根节点最远的那个点的距离。树的宽度是节点最多的一层同一层的节点距离根节点的距离都是相同的所以也可以直接枚举获得。 AC代码 Floyd使用邻接矩阵存储树先将邻接矩阵的对角线位置初始化为0某点到自己的距离为0其他位置初始化为INT_MAX/4不相连的节点理论上距离为无限大但是在计算是要考虑可能发生的溢出情况所以除以4 三层嵌套循环列举每两个点 i 和 j 之间的距离并且要考虑有中继点 k 存在的情况下两点间的距离。由于树是无环图所以只需要一个中继点即可覆盖所有情况 #include iostream #include string #include algorithm #include cmath #include vector #include map #include cstring #include queueusing namespace std; const int INF 0x7fffffff / 4; //若直接为INT_MAX则使用floyed时会发生溢出int a[105][105] { 0 }; int b[10005] { 0 };void init() {for (int i 0; i 105; i){for (int j 0; j 105; j){if (i ! j)a[i][j] INF;}} }int main() {init();int n; cin n;for (int i 1; i n - 1; i){int u, v; cin u v;a[u][v] 1;a[v][u] 2;}for (int k 1; k n; k){for (int i 1; i n; i){for (int j 1; j n; j){a[i][j] min(a[i][j], a[i][k] a[k][j]);}}}int maxdepth 0;for (int i 1; i n; i){if (maxdepth a[1][i])maxdepth a[1][i];b[a[1][i]];}int maxd 0;for (int i 1; i maxdepth; i){maxd max(maxd, b[i]);}int u, v;cin u v;cout maxdepth 1 endl;cout maxd endl;cout a[u][v] endl; }