递归树搜索以获取节点级别

2024-03-28 14:30:14 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个数据集,其中包含一棵与下面的树类似的树

  son father
1   1     NA
2   2      1
3   3      1
4   4      2
5   5     NA
6   6      2
7   7      4
8   8      5
9   9      4

构建了一个函数,允许我搜索节点(son)的整个层次结构

getTree = function(sons){
   if( length(sons) > 0 ){
      sons = subset(df, father %in% sons)[['son']]
      sons = c(sons, getTree( sons ))
   }

   return(sons)
}

subset(df, son %in% getTree(8))

这让我回过神来

  son father
4   4      2
6   6      2
7   7      4
9   9      4

但是,除了层次结构之外,还需要知道节点(子节点)位于树的哪个级别。我如何改变,或创建另一个功能,使我能够实现这一点

提前谢谢


Tags: 数据函数dfreturnif节点层次结构function
2条回答

这里可能有一个递归选项供您使用data.frame跟踪节点级别,即

f <- function(sons) {
  getTree <- function(s.df) {
    repeat {
      sons <- subset(
        df,
        father %in% s.df$sons[s.df$lvl == max(s.df$lvl)]
      )[["son"]]
      if (length(sons) == 0) {
        return(s.df)
      }
      p <- data.frame(sons = sons, lvl = max(s.df$lvl) + 1)
      s.df <- rbind(s.df, getTree(p))
    }
  }
  getTree(data.frame(sons = sons, lvl = 0))
}

其中,输入参数sons的级别始终从0开始到函数f,这样

> f(1)
  sons lvl
1    1   0
2    2   1
3    3   1
4    4   2
5    6   2
6    7   3
7    9   3

> f(2)
  sons lvl
1    2   0
2    4   1
3    6   1
4    7   2
5    9   2

> f(5)
  sons lvl
1    5   0
2    8   1

我不确定您的函数在树中到底要找到什么,但这里有一个Python示例,它可以找到表中最深的子节点以及深度。它在每次调用时使用递增的计数器来跟踪深度:

In [140]: def traverse(sons, depth=0):
     ...:     next_sons = sons[sons['father'].isin(sons['son'])]
     ...:     if len(next_sons) > 0:
     ...:         return traverse(next_sons, depth+1)
     ...:     return sons, depth

In [141]: traverse(df)
Out[141]:
(   son  father
 7    7     4.0
 9    9     4.0,
 3)

相关问题 更多 >