递归树搜索获取节点层级

Question

我有一个数据集，其中包含一棵类似于下面这棵树的树。

  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

构建了一个允许我搜索节点（子）的整个层次结构的函数

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))

那个returns我

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

但是，除了层级之外，还需要知道节点（子节点）在树的哪一层。我该如何更改或创建另一个功能来实现此目的？

提前致谢！

Answer 1

我不确定您的函数究竟要在树中查找什么，但这是 Python 中的一个示例，它在 table 中找到最深的子节点以及深度。它在每次调用时使用递增计数器来跟踪深度：

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)

Answer 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，这样

递归树搜索获取节点层级

Recursive tree search to get the node level

python

r

tree

binary-tree

binary-search-tree