The authors present cost-optimal parallel algorithms for depth-order (e.g., pre-, in-, and post-order) and level-order (e.g., breadth-first and breadth-depth) traversals of general trees with n nodes. Each of the algorithms requires O(n/p+log n) time using p>or=n processors on the EREW (exclusive read, exclusive write) PRAM (parallel random access machine) model. The breadth-first and breadth-depth algorithms attain O(log n) time complexity and yet are cost-optimal for p>or=n/log n processors. The proposed approach to the three depth-order traversals uses only a single characterization of the generic problem. The breadth-first tree-traversal algorithm utilizes a novel idea which converts this problem into a parentheses matching problem, while the breadth-depth algorithm is obtained by reducing the problem into a variety of (general) linked list ranking problems.
展开▼
机译：作者提出了具有n个节点的一般树的深度顺序（例如，前，中和后顺序）和水平顺序（例如，广度优先和广度深度）遍历的成本最佳并行算法。在EREW（排他性读，排他性写）PRAM（并行随机存取机）模型上使用p> or = n处理器时，每种算法都需要O（n / p + log n）时间。广度优先和广度算法的时间复杂度为O（log n），但对于p> or = n / log n处理器而言，其成本最优。所提出的三种深度顺序遍历的方法仅使用通用问题的单个表征。广度优先的树遍历算法利用了一种新颖的思想，将这个问题转换为括号匹配问题，而广度深度算法是通过将问题简化为各种（通用）链表排名问题而获得的。
展开▼
