첫 노드를 가리키는 포인터를 잃으면 리스트 전체 접근이 어려워집니다.
연결리스트와 트리 순회 구분 지도
연결리스트는 노드와 링크로 순서를 잇고, 트리는 부모와 자식 관계로 계층을 표현합니다.
앞뒤 링크를 바꾸는 순서가 틀리면 중간 노드가 끊어집니다.
루트, 단말, 차수, 레벨, 높이를 그림에서 직접 세어 봅니다.
전위, 중위, 후위는 루트를 언제 방문하는지로 나뉩니다.
배열과 연결리스트 비용
트리는 선형 순서보다 계층 관계와 탐색 범위 축소가 중요할 때 등장합니다.
단순 연결리스트
각 노드는 다음 노드 주소 하나만 가지고 한 방향으로 이동합니다.
이중 연결리스트
이전과 다음 링크가 있어 양방향 이동이 가능하지만 포인터 관리가 늘어납니다.
이진트리
각 노드의 자식이 최대 두 개인 트리로, 순회 문제가 자주 나옵니다.
중위 순회
왼쪽 서브트리, 루트, 오른쪽 서브트리 순서로 방문합니다.