标签: tree-traversal

我已经实现了迭代算法,其中每次迭代都涉及预订树遍历(有时称为向下累积),然后是后序树遍历(向上累积).对每个节点的每次访问涉及计算和存储要用于下次访问的信息(在随后的后序遍历或后续迭代中).

在预订序遍历期间,只要已经处理了它与根之间的所有节点,就可以独立地处理每个节点.处理完成后,每个节点都需要将元组(特别是两个浮点数)传递给每个子节点.在后序遍历中,只要已经处理了所有节点的子树(如果有的话),就可以独立处理每个节点.处理完成后,每个节点都需要将一个浮点数传递给它的父节点.

在算法期间,树的结构是静态的并且不变.但是,在向下遍历的过程中,如果传递的两个浮点数都变为零,则不需要处理该节点下的整个子树,并且可以开始该节点的向上遍历.(必须保留子树,因为后续迭代中传递的浮点数可能在此节点处变为非零并且将继续遍历).

每个节点的计算强度在整个树中是相同的.每个节点的计算是微不足道的:只需要几个总和并乘以/除以数字列表,其长度等于节点处的子节点数.

正在处理的树是不平衡的:典型节点将有2个叶子加上0-6个额外的子节点.因此,简单地将树划分为一组相对平衡的子树是不明显的(对我而言).此外,树设计为消耗所有可用的RAM:我可以处理的树越大越好.

我的串行实现仅在我的小测试树上达到每秒1000次迭代的顺序; 对于"真正的"树,我预计它可能会减慢一个数量级(或更多？).鉴于该算法需要至少1亿次迭代(可能高达10亿次)才能达到可接受的结果,我想并行化算法以利用多个核心.我对并行编程没有经验.

鉴于算法的性质,推荐的并行化模式是什么？

任何人都可以给我一个解决方案,以便在没有递归和不使用堆栈的情况下遍历二进制树的顺序？

我正在写一个广度深度优先树遍历功能,就是我想要做的是这样的:

def traverse(node):
    yield node
    for n in node.children:
        yield_all traverse(n) # << if Python had a yield_all statement

这个想法最终得到了树中的(平面)节点序列.

方法#1 :(传播产量)

def traverse(node):
    yield node
    for n in node.children:
        for m in traverse(n):
            yield m

方法#2 :(展平序列)

def traverse(node):
    return itertools.chain([node],*(traverse(n) for n in node.children))

第一种方法看起来更干净,但我觉得yield在每个级别的子树中明确指出每个节点都很奇怪.

第二种方法是简洁而略显肮脏,但它与我在Haskell中编写的内容相匹配:

traverse node = node : concatMap traverse (children node)

所以我的问题是:哪个更好？或者我错过了最好的第三选择？

我为其编写软件的系统硬件通过树结构中的硬件进行物理连接。我们应用程序中的数据模型是一棵树。对于我们的新重写，我们使用 JAXB 创建数据模型。

我们有三种类型的设备，它们都共享一些属性，所以我在 XSD 模式中创建了一个抽象设备类型。我的三个设备（推送器、切换器、接收器）都是从 XSD 中的 DeviceType 扩展而来的，如下所示：

<xs:complexType name="DeviceType" abstract="true">
  <xs:sequence>
    <xs:element name="atrr1" type="xs:int"></xs:element>
    <xs:element name="attr2" type="xs:int"></xs:element>
  </xs:sequence>
</xs:complexType>

<xs:complexType name="PusherType">
  <xs:complexContent>
    <xs:extension base="pts:DeviceType">
      <xs:sequence>
        <xs:element name="Switcher" type="pts:SwitcherType" minOccurs="1"></xs:element>
      </xs:sequence>
    </xs:extension>
  </xs:complexContent>
</xs:complexType>

<xs:complexType name="SwitcherType">
  <xs:complexContent>
    <xs:extension base="pts:DeviceType">
      <xs:sequence>
        <xs:element name="switcher" type="pts:SwitcherType" minOccurs="1"></xs:element>
        <xs:element name="receiver" type="pts:ReceiverType" minOccurs="1"></xs:element>
      </xs:sequence>
    </xs:extension>
  </xs:complexContent>
</xs:complexType>

Pusher 只有 switcher 子元素，而 switcher 可以同时有 switcher 或 receiver 子元素。接收者是线路的末端（叶节点）。xjc 构建类。我得到了 Unmarshaller 来构造对象树，但我不知道如何获得 getDevice() 的 getter 方法。对于树遍历，我希望 JAXB 会提供类似“getChildren”的东西，但我没有在 API 中看到。如果我得到一个切换器对象，我有 getSwitcher() 和 getReceiver() …

考虑具有以下属性的二叉树:

1. 如果内部节点(非叶节点)有两个子节点,则其值为1.
2. 叶节点的值为0,因为它没有子节点.

树上的级别顺序遍历将生成1和0的字符串(通过在访问每个节点时打印奇怪的值).现在给定此字符串构造二叉树并在树上执行post order遍历.后订单字符串应该是程序的输出.

例如:输入字符串是111001000.从中创建二叉树.然后在树上执行post order遍历,这将导致输出:001001011

问题的"症结"是仅从级别顺序字符串创建二叉树.我该怎么做？

对Praxis编程的这一提交给出了一个O(n)函数,它"撤消"二进制搜索树的前序遍历,将列表转换回树.提供缺失的数据声明:

data Tree a = Leaf | Branch {value::a, left::Tree a, right:: Tree a}
                 deriving (Eq, Show)

fromPreOrder :: Ord a => [a] -> Tree a
fromPreOrder [] = Leaf
fromPreOrder (a:as) = Branch a l (fromPreOrder bs)
  where
    (l,bs) = lessThan a as

lessThan n [] = (Leaf,[])
lessThan n all@(a:as)
  | a >= n    = (Leaf,all)
  | otherwise = (Branch a l r,cs)
  where (l,bs) = lessThan a as
        (r,cs) = lessThan n bs

很明显,在每个递归步骤中将一个构造函数添加到树中,这是其效率的关键.

唯一的"问题"是列表是手动穿过计算的,这不是一种非常糟糕的Haskellian方式,并且使得它更难以看到它实际上是以单线程方式逐个元素地消耗.

我尝试使用状态monad(在 …

如果我的树定义如下:

case class Node(value: Int, children: Seq[Node])

但是为了论证,让我们说访问孩子是昂贵的,所以我只想在我需要时才能遍历它们.

如果将非严格的,急切的DFS遍历Node定义为

def traverse(node: Node): Unit = {
  node.children foreach { child => traverse(child) }
}

我如何创建它的懒惰对应物？

理想情况下,我将有一个iterator方法,它返回一个基于DFS遍历排序的迭代器,它只在对其next()调用时计算下一个元素:

val tree = Node(1, Seq(Node(2, Nil), Node(3, Nil)))
val dfsIt = tree.iterator // get a iterator with a DFS traversal ordering
val nextNode = dfsIt.next() // compute which element to return on demand

我遇到了一个有趣的问题:

给定二进制树以向内螺旋顺序打印它,即第一打印级别1,然后是级别n,然后是级别2,然后是n-1,依此类推.

For Ex:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15

Should Output:
1 15 14 13 12 11 10 9 8 2 3 7 6 5 4

我想到了一个解决方案:

• 将每个级别元素存储在列表
  列表中[0] = [1]
  列表[1] = [2,3]
  列表[2] = [4,5,6,7]
  列表[3] = [8,9,10 ,11,12,13,14,15]

• 按所需顺序(0,n-1,1,n-2,...)循环列表列表并打印.以下n是在上述情况下为4的级别数.

它的空间复杂度为O(n).我相信可能有一个更好的解决方案,它有更好的空间复杂性,但我想不出它.任何人有任何指针？

虽然已经问过这个问题，但我有一个具体的实施问题。

我正在尝试打印二叉树的顶视图，以下是它的完整代码：

import java.util.*;

class Node{
    int data;
    Node right;
    Node left;
    Node(int data){
        this.data = data;
    }
}

class Pair<F,S>{
    private F first;
    private S second;
    public Pair(F first, S second){
        this.first = first;
        this.second = second;
    }
    
    public F getFirst(){return first;}
    public S getSecond(){return second;}
}

class BinaryTreeTopView{

    public static void printTopView(Node root){

        if(root == null)
            return;

    Queue <Pair<Node,Integer>> q = new Queue<>();
    Map <Integer,Node> map = new HashMap<>();
    Pair<Node,Integer> p = new Pair<>(root, 0);
    q.add(p);
    
    /*
    I …

我想知道是否有一种方法可以仅使用 vanilla JS 来选择 DOM 上的特定元素，而不必parentNode多次使用。我知道你可以用 jQuery 和修改来做到这一点Element.prototype，但还有其他漂亮的方法来写这个。

  const deleteButtons = document.querySelectorAll('.delete-button');

  for (var i = 0; i < deleteButtons.length; i++) {
    deleteButtons[i].addEventListener('click', (e) => {
      e.preventDefault();

      //This is the crazy amount of parentNode usage
      bookDatabase.child(e.target.parentNode.parentNode.parentNode.parentNode.parentNode.parentNode.getAttribute("id")).remove();
      });
    }