r - sibling 及其 child 的顺序

Question

我用括号格式表示一棵树，其中每个级别与其上层通过 { 分隔。这棵树是二元树(它可以有一个或两个 child )。我想按字母顺序对同级别的 sibling 进行排序，同时保留他们的 child 和子 child 。这意味着，只需按字母顺序对同一级别的每 2 个 child 进行排序即可。我有一个字符串 str1，其中包含输入树，我想获取字符串 str2 中的顺序。

这是一个例子:

str1<-"{A{C{D{E}}}{B{F{G{H{I}}}}}}"

在订购流程的第一阶段，我希望 str2 如下所示:

{A{B{F{G{H{I}}}}}{C{D{E}}}}

只需在 C 及其所有子级之间切换到 B 及其所有子级，然后继续...(因为 C 和 B 都是其父亲 A 的第二级。B 和 C 与 A 之间只有一个“{”分隔)我该怎么做？

Answer 1

我认为约翰的评论可能是正确的——做你想做的事情的最好方法是获取你的字符串并将其转换成正确的面向对象的树结构。随后，您可以将数据作为树而不是字符串进行操作，一旦完成操作，您可以根据需要将树结构恢复为字符串格式。 data.tree 是一个理想的包，因为它已经内置了强大的树操作工具(包括排序功能)，因此无需重新发明轮子。

幸运的是，通过递归，这种转换相对容易。以下是将字符串转换为 data.tree 的代码:

library(data.tree)

peek.next.node <- function(x){  #Helper function reads the next node (as a string) out of the char vector x
  return(paste(x[2:(which(x=="{"|x=="}")[2]-1)],collapse=""))
}

remove.next.node <- function(x){ #Helper function removes node at the start of the char vector x
  return(x[(which(x=="{"|x=="}")[2]):length(x)])
}

recurse.from.char.vector <- function (x,n){ #inspect input char vector, adding nodes to n if x starts with '{' and returning if x starts with '}'.  Will loop until return
  i<-1
  while(x[1]=="{"){
    new.node.name <- paste(c(peek.next.node(x),"_",i),collapse="")
    child.n <- n$AddChild(new.node.name,label=peek.next.node(x))
    i <- i+1
    x <- remove.next.node(x)
    x <- recurse.from.char.vector(x,child.n)
  }
  return (x[2:length(x)])
}

string.to.tree <- function(x){ #returns head node for a finished tree by calling a recursive parse function
  x.vec <- strsplit(x,"")[[1]]
  head <- Node$new(peek.next.node(x.vec),label = peek.next.node(x.vec))
  recurse.from.char.vector(remove.next.node(x.vec),head) 
  return(head)
}

请注意，即使您的节点标签超过一个字符，此代码也将起作用，并且它也适用于非二叉树。

从树返回字符串甚至更容易，因为 data.tree 对象更自然地适合递归:

recurse.to.char.vector <- function(n){
  return.vec <-unlist(c("{",n$label))
  if(length(n$children)>0)return.vec <- unlist(c(return.vec,sapply(n$children,recurse.to.char.vector)))
  return.vec <- unlist(c(return.vec,"}"))
  return(return.vec)
}

tree.to.string <- function(n){
  char.vector <- recurse.to.char.vector(n)
  return (paste(char.vector,collapse=""))
}

这是您的示例:转换、排序和转换回来:

> str1<-"{A{C{D{E}}}{B{F{G{H{I}}}}}}"
> test.tree <- string.to.tree(str1)
> str1
[1] "{A{C{D{E}}}{B{F{G{H{I}}}}}}"
> test.tree$Sort("label")
> tree.to.string(test.tree)
[1] "{A{B{F{G{H{I}}}}}{C{D{E}}}}"

请注意，您希望在单独的行上执行 Sort 和 tee.to.string - 在某些边缘情况下(例如单节点“树”) Sort() 将返回 NULL 值

在评论中，您询问“看到”没有 child ID 号的树。这可以通过在树的 levelName 属性上设置格式化函数来完成。基本上，每当您打印树时，树都会循环遍历每个节点并打印levelName属性 - 并且您可以像任何其他打印属性一样格式化它。

格式函数示例:

strip.num.from.levelName <- function(x){ #If string ends with _something, strip out everything after the last underscore
  x.vec <- strsplit(x,"")[[1]]
  which.sep <- which(x.vec == "_")
  if(length(which.sep)<=0)
    return(x)
  else 
    return(paste(x.vec[1:(tail(which.sep,1)-1)],collapse=""))
}

创建此函数后，使用 SetFormat(test.tree,"levelName",strip.num.from.levelName) 将其应用到树。这将从树的所有简单打印输出中删除该数字