고정 크기 스택을 사용하여 트리 구조 (특히 옥트리, 이진 트리의 3-D 버전)를 트래버스 할 수 있습니까? 나는 옥트리가 이기 때문에 재귀를 사용하고 싶지 않다.C/C++에서 고정 크기 스택을 사용하는 트리 순회
나는 트리를 탐색하여 범위 검색 문제를 해결하고 쿼리 한 지점과 가장 가까운 모든 점을 찾습니다. 따라서 내 탐색 영역에서 교차하지 않는 노드에 뿌리를 둔 하위 트리를 탐색하지 않습니다.
물론 네이티브 호출 스택을 사용하지 않고 연속 통과 스타일 기술을 사용하여 트리를 탐색하거나 호출 스택이 힙 데이터로 구현 된 가상 컴퓨터를 만들면 (매우 똑같습니다) 또는 명시적인 힙 데이터 구조 (예 : std::stack)로 구현 된 스택을 사용하여 스택 자동 데이터를 코딩하여 (또 다른 관점).
그렇지 않으면 C++의 순진한 코드가 Turing 머신에서 실행될 수 있으며,이 짐승에는 스택이 없습니다. Ted Hopp's answer으로
는 (일시적으로 참조 방향을 뒤집어 것을 기억하는 것이 노드 당 몇 가지 추가 비트)는 "스택없는 '통과를 가지고 Deutsch-Schorr-Waite의 가비지 컬렉션 기법에서 영감을 수 있습니다, 제안 (하지만 당신은 필요 각 노드의 추가 비트). 하지만 std::stack 또는 std::vector 내부에 자신의 스택을 갖는 것이 더 간단 할 것입니다.
_ "다른 이름으로 장미 ..."_ 연속 전달 스타일은 스택을 사용합니다. 힙을 사용하여 스택을 구현하는 것은 여전히 스택입니다. Turing 머신에서 스택을 시뮬레이션하는 것은 여전히 스택을 사용하고 있습니다. 또한, OP 스택에 대해 묻는 것, 아니 특히 전화 스택. 이 문제는 여분의 메모리 사용으로 보입니다. 명시 적으로 "스택"이라고 불리는 구조를 피하는 것이 아닙니다. –
나는 동의한다, 나는 결코 다르게 생각하지 않았다. 방금 ** 깊은 ** 네이티브 호출 ** 스택 *을 피하는 것에 대해 이야기했습니다. "깊은 재귀를 피하십시오"에 대한 나의 이해는 기계 스택에 관한 것입니다. –
당신의 octree에 부모 포인터가 있다면, 스택없이 포인터를 탐색 할 수 있다고 생각합니다 (예 : this thread 참조). 그것이 없으면 몇개의 가지가 건너 뛸 지에 관계없이 나무의 깊이만큼 깊은 더미가 필요할 것입니다.
예 고정 크기 스택을 사용하여 팔순을 탐색 할 수 있습니다.
고정 크기는 가능한 가장 긴 옥트리 깊이만큼 커야합니다.
옥트리로, 각 깊이 탐색은 단지 3 비트의 메모리로 기록 될 수 있다는 것을 명심하십시오. 세 가지 차원 각각에 대해 긍정적이거나 부정적인 방향으로 기록했는지 만 기록하면됩니다.
따라서 octree가 1000- 깊이 가더라도 375 바이트로 재귀를 저장할 수 있습니다.
고정 크기 스택이 아닙니다. 임의의 고정 된 N에 대해, N 바이트로 재귀를 저장할 수없는 깊이가 8 배가 될 것이다. (10^-1000) * log (N)은 여전히 O (log N)입니다. –
@TedHopp : 당신의 수학은 정확 합니다만, "깊이가 너무 깊어 질 것입니다"는 이론적 인 가정입니까? 이것은 현실 세계의 문제인 것 같습니다. –
가능한 [Traverse tree without recursion and stack in C] (http://stackoverflow.com/questions/3214312/traverse-tree-without-recursion-and-stack-in-c) – thiton
나는 당신이 기계의 호출 스택 크기에 대한 실질적인 제한 때문에 재귀를 피하기를 원합니다. –