1
재귀를 사용하지 않고 복합 (트리) 구조의 반복자를 작성하거나 작성한 사람이 있습니까? 그렇다면 아이디어를 공유 할 수 있습니까? Thks재귀가없는 복합 패턴 반복자
편집 : 나는 Java 언어를 생각하고있었습니다.
A
답변
1
재귀없이 트리를 순회하는 것은 충분히 간단합니다. 이진 트리를 가정하면, 각 노드는 아마도 다른 노드에 대한 세 개의 참조를가집니다. 왼쪽 자식, 오른쪽 자식 및 부모. 깊이 우선 왼쪽에서 오른쪽 반복 순서를 가정하면 while-lop (의사 코드 while current.left-child != null, current = current.left-child) 의 왼쪽 자식 참조를 따르고 왼쪽 자식이 없으면 올바른 자식을 시도합니다. 올바른 아이도없는 경우, 오른쪽 아이를 찾을 때까지 올라갑니다 (while current.right-child == null, current = current.parent)
언어를 지정하지 않았지만 재귀를 피하기 위해 필자는 반드시 그것이 필수적이라고 가정 할 것입니다. 어떤 종류의 언어, 그리고 위의 것이 가능해야합니다.
즉, 반복자는 현재 노드에 대한 참조와 이동 경로에 대한 정보를 보유해야합니다.
0
다음과 같은 질문에서 영감을 얻을 수 있습니다. Post order traversal of binary tree without recursion 필요한 것은 이진 트리가 아닌 알고리즘으로 알고리즘을 확장하는 것입니다.
이진 트리 탐색에 동의하지만 이진 트리를 가정하고 싶지 않습니다. – Vidhya
글쎄, 그것의 구조에 대해 일종의 가정을하지 않고 나무를 가로 지르기는 어렵다. 동일한 접근 방식은 트리 구조에 따라 쉽게 수정할 수 있습니다. 자녀를 통과 한 다음 부모까지 가서 다음 자식 노드를 시도하십시오. – jalf