在没有递归的情况下遍历非二叉树的算法是什么(使用堆栈)?
直觉上,我知道我像(node, iterator)一样保持堆栈对,但我仍然无法找到工作解决方案. 解决方案 您总是可以将递归算法转换为具有显式堆栈的递归算法.从递归代码开始: void traverse(NODE *p) { if (p) { for (int i = 0; i n_children; ++i) { traverse(p->child[i]); } } } 替换递归调用: struct { NODE *p; int i; } stk[MAX_RECURSION_DEPTH]; int sp = 0; void traverse(NODE *p) { start: if (p) { for (int i = 0; i n_children; ++i) { // Save local values on stack. stk[sp].p = p;
0 2024-01-23
编程技术问答社区
只需按相同的顺序插入节点,就能从Preorder中获得BST
要从给定的预订遍历中构造BST,如果我尝试以与预订相同的顺序插入BST,我会得到BST. 因此,我们不通过排序元素或执行任何其他Alogrith? 来创建秩序 是否有一个示例表明不能仅通过插入元素来构造树? 解决方案 您是正确的...您可以按照预订遍历的顺序插入节点以重建树. 插入的第一个节点必须放在正确的位置,因为它是根,而预订的遍历始终首先放置根.预订遍历中的下面是左子树的预订布局,然后是右子树.当插入左子树节点时,通过从根部向左插入它们,然后递归地在该子树上应用相同的过程.右子树以相同的方式进行重建.使用归纳,如果您喜欢. ,您可以正式证明这一点 希望这会有所帮助!
0 2024-01-23
编程技术问答社区
彬彬有礼树后序遍历,无递归,无节点标志
还有另一种方法吗?只是花了2个小时来弄清楚它.我有一个解决方案(请参阅下面的Dumppostorder),但是,是否有更好或更有效的方法?感觉可能有.规则是 - 没有递归,节点不能具有访问的标志.即,您只能使用左 +右成员. 我的方法是在此过程中摧毁这棵树.通过将双方的孩子设置为null,您可以将节点标记为一次遍历一次,但是我也可以两次与孩子一起看每个节点:(.有更好的方法吗?但没有必要(即,将投票,但不会标记答案).谢谢! using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace BinaryTreeNoRecursion { public class TreeNode { public T Value { get; set; } public TreeNode Left { g
0 2024-01-23
编程技术问答社区
如何用它的BFS和DFS遍历构建一棵树
我有一棵树的BFS和DFS遍历.如何从这些遍历中重建树? 例如: BFS Traversal : 4 3 5 1 2 8 7 6 DFS Traversal : 4 3 1 7 2 6 5 8 然后,树就像波纹管: 4 / \ 3 5 / \ \ 2 1 8 | | 6 7 解决方案 仅当bfs和dfs使用恰好相同的顺序遍历孩子: 规则1: BFS Traversal : 4 3 5 1 2 8 7 6 | | | | | |-------| | | | DFS Traversal : 4|3 1 7 2 6|5 8 如本示例所示,我们很容易地知道(3 , 1 , 7 , 2 , 6)属于具有3个根的子
2 2024-01-23
编程技术问答社区
广度优先的搜索树怎么能包括一个交叉边缘?
好吧,我知道一个无向图的广度优先搜索树没有后边缘.但是我想知道它怎么能具有交叉边缘?我无法成像由OFS构造的图G的一生成树,其中包含一个交叉边缘. 解决方案 使用BFS在无向图上建造生成树的过程将生成以下类型的边缘: 树边缘 交叉边缘(在不同分支上连接顶点) 一个简单的示例:想象一个三角形(一个三角形集团) - 从任何节点启动BFS,您将在第一步到达其他两个.您之间的边缘不属于生成树. 背部边缘(将祖先与非Immendiate儿童联系起来)?好吧,正如您指出的那样,在BFS上,您不会拥有它们,因为您在第一次到达祖先时会使用该边缘. 实际上,您可以做出更强大的语句 - 所有非树边缘都应在顶点之间作为相同级别或相邻的级别(如果另一侧的Vertice是兄弟姐妹,就像在三角案中或父母的兄弟姐妹一样,尚未探索).无论哪种方式,它都属于交叉边缘的定义. 其他解决方案 我也有同样的问题...答案是BFS中没有跨边缘,但是BFS tree本身编码所有本来可以回来
0 2024-01-23
编程技术问答社区
在O(logn)时间复杂度中,BST的中位数
我遇到了在但是可以使用O(logn)时间实现相同的时间吗?这里也问了同样的问题 - 解决方案 如果您还维护节点的左和右后代数量的计数,则可以通过搜索中位置位置来在O(logn)时间中进行操作.实际上,您可以在O(logn)时间中找到KTH最大元素. 当然,这假定树是平衡的.维护计数不会改变插入/删除复杂性. 如果树未平衡,则您的欧米茄(N)最坏情况. 请参阅:订购统计统计树. 顺便说一句,Bigo和Smallo非常不同(您的标题为Smallo). 其他解决方案 除非您保证某种平衡的树,否则不可能. 考虑一棵完全退化的树 - 例如,每个left指针都是无效的(nil,whitch),因此每个节点只有一个正确的孩子(即,对于所有实际目的,"树"确实是单一链接的列表). 在这种情况下,只需访问中间节点(根本)就需要线性时间 - 即使您开始知道节点n是中位数,仍然需要n个步骤才能到达该节点. 其他解决方案 我们可以使用rabbit和turtl
4 2024-01-23
编程技术问答社区
在O(logn)时间复杂度中,BST的中位数
我遇到了在但是可以使用O(logn)时间实现相同的时间吗?这里也问了同样的问题 - 解决方案 如果您还维护节点的左和右后代数量的计数,则可以通过搜索中位置位置来在O(logn)时间中进行操作.实际上,您可以在O(logn)时间中找到KTH最大元素. 当然,这假定树是平衡的.维护计数不会改变插入/删除复杂性. 如果树未平衡,则您的欧米茄(N)最坏情况. 请参阅:订购统计统计树. 顺便说一句,Bigo和Smallo非常不同(您的标题为Smallo). 其他解决方案 除非您保证某种平衡的树,否则不可能. 考虑一棵完全退化的树 - 例如,每个left指针都是无效的(nil,whitch),因此每个节点只有一个正确的孩子(即,对于所有实际目的,"树"确实是单一链接的列表). 在这种情况下,只需访问中间节点(根本)就需要线性时间 - 即使您开始知道节点n是中位数,仍然需要n个步骤才能到达该节点. 其他解决方案 我们可以使用rabbit和turtl
0 2024-01-23
编程技术问答社区
在完整树的深度第一和广度第一的遍历之间进行转换的函数
问题:考虑一棵具有L级别的完整的K-Ary树,其节点标记为其等级的广度首次遍历.按以深度遍历的顺序计算标签列表. 例如,对于具有3个级别的二进制树,所需的列表是: [0 1 3 7 8 4 9 10 2 5 11 12 6 13 14] 做到这一点的一种方法是实际构造树结构并两次穿越;第一个遍历首先是宽度,标记节点0,1,2,..第二个遍历首先是深度,报告标签0,1,3,7,.. 我对避免在内存中构造树的方法感兴趣.我意识到,这种树的大小与输出的大小相当,但是我希望该解决方案将允许"流"输出(即不需要完全存储在内存中的输出). 我也对同伴问题感兴趣;从根据深度的第一遍历标记的树开始,然后产生广泛的第一个遍历的标签.我认为解决这个问题的解决方案在某种意义上将是第一个问题的双重问题. 解决方案 您实际上不需要构造树.您可以仅使用BFS标签而不是指针到实际节点的深度遍历深度. 使用BFS位置标签表示k-ary树中的节点: 根为0 任何节点的第一个孩
4 2024-01-23
编程技术问答社区
脚本中的树形遍历算法
我需要以深度的第一种方式来遍历树结构.我无法提出算法正确执行此操作. 我的输入是: [ ["A", "B", "C"], ["1", "2"], ["a", "b", "c", "d"] ] 输出应采取表格: [ "A/1/a", "A/1/b", "A/1/c", "A/1/d", "A/2/a", "A/2/b", "A/2/c", "A/2/d", "B/1/a", "B/1/b", "B/1/c", "B/1/d", "B/2/a", "B/2/b", "B/2/c", "B/2/d", "C/1/a", "C/1/b", "C/1/c", "C/1/d", "C/2/a", "C/2/b", "C/2/c", "C/2/d" ] 解决方案 这应该完成工作: 在 function traverse(arr) { var first = arr[0]; var r
4 2024-01-23
编程技术问答社区
级序遍历的时间复杂度
二进制树水平顺序遍历的时间复杂性是多少?是o(n)还是o(log n)? void levelorder(Node *n) { queue q; q.enqueue(n); while(!q.empty()) { Node * node = q.front(); DoSmthwith node; q.dequeue(); if(node->left != NULL) q.enqueue(node->left); if (node->right != NULL) q.enqueue(node->right); } } 解决方案 它是O(n),或者是准确的Theta(n). 在树上的每个节点上都有一个查看 - 每个节点最多被"访问",至少一次) - 当发现(
2 2024-01-23
编程技术问答社区
为什么内序和前序遍历对于创建一个决定T2是否是T1的子树的算法来说是有用的?
我正在看一本采访书,问题是: 您有两棵非常大的二进制树:T1,有数百万个节点, T2,有数百个节点.创建一种算法来决定T2是否是 T1的子树. 作者将其称为可能的解决方案: 请注意,这里的问题指定T1有数百万 节点 - 这意味着我们应该小心使用多少空间. 假设,例如,T1有1000万个节点,这意味着 仅数据大约40 mb. 我们可以创建一个代表 在秩序和预订遍历.如果T2的预订遍历是 T1的预订遍历的子字符串,T2的inorder traversal是一个 T1的内存遍历的子字符串,然后T2是T1的子字符串. 我不太确定为什么这些是真的的逻辑: T2-preorder-traversal-string是T1-preorder-traversal-string 的子字符串 T2-inorder-traversal-string是T1-inorder-traversal-string 的子字符串 T2必须是T1的substring(尽管我认为作者为su
0 2024-01-23
编程技术问答社区
现实世界中的前/后序树形遍历实例
我了解预购,按处和后树遍历算法的良好. (参考).我了解一些用途:用于遍历二进制搜索树的秩序,预订以克隆树.但是我一生无法提出一个现实世界的任务,我需要后订单遍历才能完成. 你能给我一个例子吗?而且:您能给我任何更好的预订遍历吗? 编辑:除了表达树和RPN以外,有人可以给我一个例子吗?这真的所有的后订单都适合? 解决方案 拓扑排序是树木的后订单遍历(或定向的acyclic图形) ). 这个想法是图表的节点表示任务,而从A到B的边缘表示必须在B之前执行A.拓扑排序将以顺序排列这些任务,以使任务的所有依赖项都比任务本身更早.任何构建系统,例如 unix make 必须实现此算法. Dario提到的示例 - 用手动记忆管理破坏树的所有节点 - 是此问题的一个实例.毕竟,销毁节点的任务取决于其儿童的破坏. 其他解决方案 正如Henk Holterman指出的那样,使用手动记忆管理销毁树通常是后订单遍历. 伪代码: destroy(node) {
2 2024-01-23
编程技术问答社区
后阶图遍历?
鉴于下面的有向图,我们如何实现后订单遍历? dfs 预订遍历中的访问顺序:1 2 5 4 6 3 在后阶段的访问顺序:4 6 5 2 1 3 解决方案 后阶DFS基本上具有以下设计: 访问孩子们; 拜访自己; 从1开始,按以下顺序探索节点: 1 - > 2 - > 5 - > 4(v) - > 6(v) - > - > 5(v) - > 2(v) - > 2(v) - > 1(v) - > 1(v) - > 3(v) 在这里(v)暗示该节点在看到没有一个孩子没有被访问或至少他们正在访问中后访问.这解释了为什么遍历为465213. 可能是什么让您感到困扰的是我们访问节点3的方式,因为从1开始,没有通往3的路径.答案似乎是扫描了整个连接图后,如果剩下任何未频率的节点,则遍历算法扫描.因此,它最终在末尾访问3
10 2024-01-23
编程技术问答社区
我们可以将Morris Traversal用于邮局吗?
我访问了许多网站,但找不到莫里斯邮政遍历的任何算法. 我知道我们可以将莫里斯算法用于预订和inorder.如果有人将我指向Morris算法(如果存在). 解决方案 一种更简单的方法是与莫里斯遍历的对称相反,并以相反的顺序打印节点. TreeNode* node = root; stack s; while(node) { if(!node->right) { s.push(node->val); node = node->left; } else { TreeNode* prev = node->right; while(prev->left && prev->left != node) prev = prev->left; if(!prev-
10 2024-01-23
编程技术问答社区
有空元素的内序、前序和后序遍历的唯一性
我们都知道,不同的二进制树可以具有相同的 inorder , preorder ,或 postorder traversal.但是,如果我们将null元素包括在 preorder 遍历中,那么只要树是唯一的,遍历的结果将是唯一的.考虑这两棵树: 3 3 / \ 4 vs. 4 它们的正常 pre -em traversal均为{3,4},但是如果我们包括null元素,那么它们的遍历将分别为{3,4,null,null,null}和{3,null,4,null,null},使遍历遍历唯一. 我的问题是,对于秩序和后订单遍历也是如此吗?我们怎么能证明它? 解决方案 对于后订单遍历是正确的,因为那只是反向树的前订单遍历的相反. 对于内存遍历而言,这始终以null开始,以null和Nulls和Nodes之间的交替开始. .
4 2024-01-23
编程技术问答社区
打印二叉树中从根到叶的所有路径
这是我写的代码,要打印从根到叶的二进制树的所有路径: public static void printRootToLeaf(Node1 root, List list) { if(root == null) { return; } list.add(root.data); if(root.left == null && root.right == null) { System.out.println(list); return; } printRootToLeaf(root.left, list); printRootToLeaf(root.right, list); } 我以这样的主要方式称此方法: public static void main(String[] args) { Node1 root = new N
4 2024-01-23
编程技术问答社区
解释Haskell广度第一的编号代码来遍历树木
我正在阅读一个问题是 - 魔术在算法中如何发生?有一些数字(例如,图7的标题为"将一个级别的输出螺纹到下一个级别的输入") 不幸的是,也许只有我,但是这个数字使我感到困惑.我根本不明白螺纹是如何发生的吗? 解决方案 广度第一遍历意味着逐一遍历树的遍历.因此,假设我们已经知道每个级别开始时的数字是什么 - 在每个级别之前远距离元素的数量.对于论文中的简单示例 import Data.Monoid data Tree a = Tree (Tree a) a (Tree a) | Empty deriving (Show) example :: Tree Char example = Tree (Tree Empty 'b' (Tree Empty 'c' Empty)) 'a' (Tree Empty 'd' Empty) 大小将是0、1、3、4.知道这一点,我们可以通过给出树(子树(子树)从左到右进行此类尺寸的列表:我们通过一个用于节点,然
0 2024-01-23
编程技术问答社区
有大量文件的目录结构的树形遍历算法
当递归遍历目录结构时,如果您的文件多于目录,则最有效的算法是什么?我注意到,当使用深度优先遍历时,当给定目录中有很多文件时,似乎需要更长的时间.在这种情况下,广度优先的遍历是否更有效?目前我无法介绍这两种算法,因此非常欢迎您的见解. 编辑:响应Alphazero的评论,我正在使用Linux机器上的PHP. 解决方案 广度优先会更好.输入根文件夹时,您可以创建需要处理的项目列表.其中一些项目是文件,有些是目录. 如果您使用广度优先,则将处理目录中的文件,然后在转到一个儿童目录之前就忘记它们. 如果您首先使用深度优先,则需要继续增加文件列表以稍后进行深入研究.这将使用更多内存来维护您的文件列表来处理,可能会导致更多页面故障等... 加上,无论如何,您都需要浏览新项目的列表,以确定哪些是可以钻入的目录.当您到达处理文件时,您将需要再次浏览相同的列表(减去目录). 其他解决方案 由于您的文件比目录更多,因此看起来好像您正在处理非常嵌套的目录,这些目录会使D
0 2024-01-22
编程技术问答社区
前序到后序的遍历
如果二进制搜索树的预订遍历为6、2、1、4、3、7、10、9、11,如何获得后阶遍历? 解决方案 您获得了树的预购遍历,该遍历是通过:输出,左侧,右遍历的构造. . 由于后阶遍历来自BST,您可以通过对数字进行排序,从后阶遍历中推断出内顺序(左侧,输出,右输出).在您的示例中,订购遍历为1、2、3、4、6、7、9、10、11. 从两个遍历中,我们可以构造原始树.让我们为此使用一个更简单的示例: 预订:2,1,4,3 订购:1、2、3、4 预购遍历使我们的树的根为2.在阶数中,告诉我们1落入左下的子树中,3个落入右侧的子树中.左子树的结构很琐碎,因为它包含一个元素.正确的子树的预订遍历是通过从原始的预订遍历中获取该子树中元素的顺序来推导的:4,3.我们知道,我们知道右子树的根为4,并且从临时遍历(3,4)中,我们知道3落入左下角.我们的最后一棵树看起来像这样: 2 / \ 1 4 / 3 使用树结构,我们可以通过漫步树来获得
2 2024-01-22
编程技术问答社区
二叉树的级序遍历
void traverse(Node* root) { queue q; Node* temp_node= root; while(temp_node) { coutvalueleft) q.push(temp_node->left); if(temp_node->right) q.push(temp_node->right); if(!q.empty()) { temp_node = q.front(); q.pop(); } else temp_node = NULL; } } 上面发布的代码是我的级别订单遍历代码.这个
2 2024-01-22
编程技术问答社区