핵심 요약
Microsoft Developer가 부모 포인터를 활용한 이진 트리의 비재귀·상수 공간 삭제 알고리즘을 제시합니다. 인오더 순회를 차용한 흐름을 N-ary 포스트오더 방식으로 적용해, 왼쪽으로 깊이 내려가고 더 이상 왼쪽이 없으면 오른쪽으로 이동한 뒤 자식을 삭제하고 상위로 되돌아가며 남은 부분을 처리합니다.
구현 방법
- Node 구조체: left, right, parent, Data d를 포함하는 C++ 스타일 구현
- 왼쪽 하위가 있으면 계속 내려가고, 없으면 오른쪽으로 한 걸음 간 뒤 다시 왼쪽으로 탐색
- 바닥에서 노드를 삭제하고 부모로 올라가며, 왼쪽 자식으로 왔는지에 따라 다음으로 오른쪽 자식을 진행하는지를 결정
- NextSibling은 부모의 자식 위치를 이용해 "왼쪽이면 오른쪽이 다음"으로 합성
- 핵심은 재귀 없이 포인터 관리로 트리를 순회하며 해제하는 흐름
주요 결과
- 상수 공간으로 트리 전체 해제가 가능, 깊은 트리도 스택 없이 처리
- 메모리 해제와 정리 과정의 안정성 확보
