标签: traversal

我是Haskell的新手,所以我想弄清楚如何进行树遍历.

以下是我在几篇论文中看到的公司示例(略有变化)

data Company  = C [Dept]               deriving (Eq, Show, Typeable, Data)
data Dept     = D Name Manager [Unit]  deriving (Eq, Show, Typeable, Data)
data ThinkTank= TK Name [Unit]         deriving (Eq, Show, Typeable, Data)
data Unit     = PU Employee | DU Dept  deriving (Eq, Show, Typeable, Data)
data Employee = E Person Salary        deriving (Eq, Show, Typeable, Data)
data Person   = P Name Address         deriving (Eq, Show, Typeable, Data)
data Salary   = S Float                deriving (Eq, Show, Typeable, Data)
type …

我试图找到一种方法来返回数组的父键的值.

例如,从下面的数组我想找出父元素的键,其中$ array ['id'] =="0002".父键是显而易见的,因为它在这里定义(它将是'产品'),但通常它是动态的,因此问题.但是'id'的'id'和值是已知的.

    [0] => Array
        (
            [data] => 
            [id] => 0000
            [name] => Swirl
            [categories] => Array
                (
                    [0] => Array
                        (
                            [id] => 0001
                            [name] => Whirl
                            [products] => Array 
                               (
                                    [0] => Array
                                        (
                                            [id] => 0002
                                            [filename] => 1.jpg
                                         )
                                    [1] => Array
                                        (
                                            [id] => 0003
                                            [filename] => 2.jpg
                                         )
                                )
                         )
                 )
          )

我想知道如何最好地实现树数据结构,以便能够枚举所有级别的路径.让我用下面的例子解释一下:

     A
   /   \
   B    C
   |    /\
   D   E  F

我希望能够生成以下内容:

A
B
C
D
E
F
A-B
A-C
B-D
C-E
C-F
A-B-D
A-C-E
A-C-F

截至目前,我正在对使用字典构建的数据结构执行深度优先搜索,并记录可见的唯一节点,但我想知道是否有更好的方法来执行此类遍历.有什么建议？

我不清楚抽象语法树的结构.要在AST代表的程序源中"向下(向前)",你是在最顶层的节点上走,还是走下去？例如,是示例程序

a = 1
b = 2
c = 3
d = 4
e = 5

导致AST看起来像这样:

或这个:

在第一个中,在右边的"右边" main node将推进你通过程序,但在第二个中,只需跟随next每个节点上的指针将执行相同的操作.

似乎第二个更正确,因为您不需要像第一个节点那样具有可能极长的指针数组的特殊节点类型.虽然,当你进入for循环和if分支以及更复杂的事情时,我可以看到第二个变得比第一个变得复杂.

在重新创建CMS时,我想要替代传统的父/子方法来管理站点地图/页面层次结构.我记得有一段时间看到嵌套的模型,但是不记得它叫什么了.所以,我偶然发现了一个类似的方法,我想评估和比较属性,确保我不会在以后遇到愚蠢的限制,因为我没有采用已经过时间测试的方法.所以,请告知A)它是否已经被发明(它叫什么？!),B)属性中存在根本缺陷,或者C)这是一个很好的方法(请给出正确的理由!).

考虑这个清单:

• 家
  • 关于我们
  • 联系我们
  • 制品
    • 服装
    • 图书
    • 电子产品
  • 知识库
  • 其他的东西

在嵌套集模型下,我相信您使用深度优先遍历存储每个节点的左/右描述符:

Home                  1-18
    About Us          2-3
    Contact Us        4-5
    Products          6-13
        Clothing      7-8
        Books         9-10
        Electronics  11-12
    Knowledge Base   14-15
    Other stuff      16-17

这是我开始喜欢的"错误方式":

Home                  1-9
    About Us          2-2
    Contact Us        3-3
    Products          4-7
        Clothing      5-5
        Books         6-6
        Electronics   7-7
    Knowledge Base    8-8
    Other stuff       9-9

我存储的是ID和LAST_CONTAINED_ID,而不是左/右对.我发现许多属性都是相同的(或非常相似):

• 根节点是ID = 1
• 对于"叶子",两个属性是相等的,而对于分支,它们不是
• 任何给定节点的"子节点"总数为LAST_CONTAINED_ID - ID
• 所有包含的节点都有一个ID>容器的ID,但<=容器的LAST_CONTAINED_ID
• 祖先节点的ID <子ID,但是LAST_CONTAINED_ID> =子ID
• 深度是祖先节点的SUM

此外,ID提供特定于订单的唯一标识符(没有间隙!).为了简单起见,我发现存储DEPTH和PARENT参考也更容易,但对于嵌套集来说,这与我的理解基本相同.

那么,这算作嵌套吗？它是否已经是一种常见的方法(但为什么我之前没有听说过......)？我有理由在这个上使用真正的嵌套集吗？

我欢迎你的想法.

是否可以std::stack在C++中遍历？

使用以下方法遍历不适用.因为std::stack没有会员end.

std::stack<int> foo;

// ..

for (__typeof(foo.begin()) it = foo.begin(); it != foo.end();  it++)
{
    // ...
}

在NLTK中,如何遍历已解析的句子以返回名词短语字符串列表？

我有两个目标:
(1)创建名词短语列表,而不是使用'traverse()'方法打印它们.我目前使用StringIO来记录现有traverse()方法的输出.这不是一个可接受的解决方案.
(2)解析名词短语字符串,以便:'(NP Michael/NNP Jackson/NNP)成为'Michael Jackson'.在NLTK中有解除解析的方法吗？

NLTK文档建议使用traverse()来查看名词短语,但是如何在这个递归方法中捕获't',以便生成一个字符串名词短语列表？

from nltk.tag import pos_tag

def traverse(t):
  try:
      t.label()
  except AttributeError:
      return
  else:
      if t.label() == 'NP': print(t)  # or do something else
      else:
          for child in t: 
              traverse(child)

def nounPhrase(tagged_sent):
    # Tag sentence for part of speech
    tagged_sent = pos_tag(sentence.split())  # List of tuples with [(Word, PartOfSpeech)]
    # Define several tag patterns
    grammar = r"""
      NP: {<DT|PP\$>?<JJ>*<NN>}   # chunk determiner/possessive, adjectives and noun
      {<NNP>+}                # chunk sequences of proper nouns
      {<NN>+}                 # …

我希望递归遍历以下树结构尾部而不回退循环:

const o = {x:0,c:[{x:1,c:[{x:2,c:[{x:3},{x:4,c:[{x:5}]},{x:6}]},{x:7},{x:8}]},{x:9}]};

        0
       / \
      1   9
    / | \ 
   2  7  8
 / | \
3  4  6
   |
   5

期望的结果: /0/1/2/3/4/5/6/7/8/9

我想需要一个闭包来启用尾递归.到目前为止我试过这个:

const traverse = o => {
  const nextDepth = (o, index, acc) => {
    const nextBreadth = () => o["c"] && o["c"][index + 1]
     ? nextDepth(o["c"][index + 1], index + 1, acc)
     : acc;

    acc = o["c"]
     ? nextDepth(o["c"][0], index, acc + "/" + o["x"]) // not in tail pos
     : …

所以我知道遍历顺序的递归的空间复杂度是O(h)而不是O(n),因为h =树高度,n =树中节点的数量.

这是为什么？让我们说这是遍历的代码:

public void inorderPrint (TreeNode root) {

    if (root == null) {
        return;
    }

    inorderPrint(root.left);
    System.out.println(root.data);
    inorderPrint(root.right);

}

我们将n个内存地址推送到调用堆栈,因此,空间复杂度应为O(n).

我错过了什么？

我知道我可以遍历List小号

import cats.instances.list._
import cats.syntax.traverse._

def doMagic(item: A): M[B] = ???
val list: List[A] = ???
val result: M[List[B]] = list.traverse(doMagic)

我可以Seq来回转换List

val seq: Seq[A] = ???
val result: M[Seq[B]] = seq.toList.traverse(doMagic).map(_.toSeq)

但是我可以在Seq没有样板的情况下进行遍历吗？

val seq: Seq[A] = ???
val result: M[Seq[B]] = seq.traverse(doMagic)

或者,获取Traverse [Seq]实例的简单方法是什么？