R 중첩 된리스트를 간단한 이진 트리로 사용하기

저는 R에 제약이되는 간단한 문제가 있습니다. 실제로 터미널 말단에만 관련 값이있는 이진 트리가 있습니다. 장난감 예제가 표시됩니다. here.
본질적으로 잎 사이에서 최대 깊이의 작업을 수행합니다 (깊이가 같은 순서는 중요하지 않음). 나는 그것을 여기에 추가했다. 그러나 실제로, 그들은 더 복잡한 공식에 꽂혀있다.
내 코드는 R로 제한됩니다. 이 구조는 내가 다른 수단을 통해 그것을 얻을 수 있지만,이 명령으로 표현 될 수있다 : 내가 가장 깊은 수준이 얼마나 깊은 결정하는 작업 기능이R 중첩 된리스트를 간단한 이진 트리로 사용하기

testBranch<-list(list(list(list(20,15),40),list(10,30)),5) #Depth of 4

하지만, R에서 중첩 된 목록을 불허한다. 어떤 단서를 효율적으로 찾을 수 인덱스 가장 깊은 값을 액세스하려면? 내가 원하는 걸 줄 것

testBranch[[1]][[1]][[1]]

위의 장난감 예 예, 들어, 목록 2 개 요소를 포함. 내 또한 예제를 사용하여, 나는 다음이 작업을 수행 할 수 있습니다 :

testBranchStep1<-list(list(list(35,40),list(10,30)),5)

내가 :

indexesOI<-getIndexes(testBranch) testBranch[indexesOI]<-testBranch[indexesOI][1]+testBranch[indexesOI][2] #testBranch now has depth of 3

에 의해 R로 표현 될 수있는 toy example, 1 단계에 해당하는 트리의 결과 필요한 경우 패키지를 사용하여 개방하십시오. 클래스 시스템에 대한 많은 경험이 없기 때문에 R에서 전체 노드 클래스/dfs를 다시 작성하지 않으려 고합니다. data.tree를 살펴 봤지만 중첩 목록을 데이터 구조로 강요하는 행운은 없었습니다.

도움이된다면 도움이 될 것입니다. 급하게 만든 ASCII 나무를 용서하십시오. 나는 주로 독학으로 많은 질문을하지 않았으므로, 서식을 조정해야 할 필요가 있으면 알려 주시기 바랍니다! 감사!

출처

2017-10-24 Nick Fisk

를 알 수 없기 때문에 여기에 의사 코드에서 재귀 함수입니다.

 levelName 
1 Root   
2 °--1   
3  ¦--1  
4  ¦ °--1 
5  °--2

data.tree 많은 유틸리티 함수와 속성을 (당신이 네트를 읽을 수 있는지 확인)은 다음과 같은 기능을 제공

library(data.tree) 
testBranch <- list(list(list(list(20,15),40),list(10,30)),5) 
tree <- FromListSimple(testBranch) 
tree

이

트리를 인쇄합니다.깊이를 알고, 특히, 이것을 사용 :

height <- tree$height

산출 어느 :

maxDepthLeaves <- Traverse(tree, filterFun = function(node) node$level == height)

이를 : 그런 다음 트리를 탐색 및 최대 높이 노드를 찾을 수 있습니다

> 4

traversal은 최대 레벨의 노드 목록입니다 (이 경우 하나만 Node). 그런 다음 Get을 사용하여 임의의 값을 트래버스에서 검색 할 수 있습니다. name의 position, 또는 pathString : 나는 지금까지 전에이 입수했습니다

  1 
"Root/1/1/1"

출처

2017-10-25 05:19:46

Get(maxDepthLeaves, 'pathString')

는 다음과 같이 표시. 그 이후로 더 많은 것을 가지고 놀았지만, 나는 여전히 내 질문에 언급 된 바와 같이 그 깊이에서 잎에 경로/인덱스를 얻는 방법을 찾지 못했습니다.> _Any 단서 가장 깊은 값에 접근하기 위해 인덱스 세트를 효율적으로 찾는 방법 ? _ 모든 분기를 수동으로 반복하지 않고 data.tree 구조를 활용하는 방법을 알고 있습니까? 제 질문의 핵심은 가장 깊은 나뭇잎의 위치를 찾는 것과 관련이 있습니다. 지금까지 도와 주셔서 대단히 감사합니다! –

완벽합니다. 정말 고맙습니다. 어떤 시점에서 네이티브 목록을 사용하는 현명한 방법을 찾아 내고 싶지만, 이것은 내 목적에 잘 맞습니다! 방법을 파악하자마자 답변으로 표시 할 것입니다. –

중간에있는 것처럼 들리 네요. 가장 깊은 노드를 찾을 때마다 색인을 목록에 출력 할 수 있습니다. 나는 당신이 data.tree하여이 작업을 수행 할 수 R.

If tree is a leaf node 
    If current depth is greater than max-depth 
     Delete list of indices 
     Append current index into list of indices 
    If current depth is equal to max-depth 
     Append current index into list of indices 
Else 
    for each element in the tree 
     Get current index 
     Recursively call this function, passing in the current index

출처

2017-10-25 00:03:51 Andrew

R 중첩 된리스트를 간단한 이진 트리로 사용하기

답변

관련 문제