스레드 이진트리 개념

소개글

자료구조에서 스레드 이진트리 개념과 장점,단점 등을 간단하게 요약정리한것입니다.

목차

없음

본문내용

1.
어떤 노드의 좌측 포인터가 널포인터라면 그 노드의 선행자 노드(前노드)를 지적 하도록 포인터값을 설정한다
2.
어떤 노드의 우측 포인터가 널포인터라면 그 노드 다음에 운행되는 노드(後노드)를 지적하도록 포인터 값을 설정한다
스레디드 이진 트리 장점
1.
순회를 한후 다음 노드로 가기위해 왔던 노드들을 다시 지나가는 것을 불필요한 작업을 제거할 수 있다.
2.
기억 공간의 낭비를 최소화 할 수 있음
3.
트리의 운행 속도가 빨라진다.
스레디드 이진 트리의 단점
1.
정상 포인터와 스레드 포인터를 구별하기 위해 여분의 기억 장소가 필요하다
1) 전위 운행 스레드 이진 트리
- 트리에서 스레드를 제거한 후 이진 트리를 전위 운행 :
A B D C E G F H I가 된다.
- 스레드는 자식 노드가 없는 연결 부분에만 붙여진다.
- 예) 노드 B는 왼쪽 자식 노드는 존재하고 오른쪽 자식 노드는 없다.
→ 왼쪽 연결 부분에는 스레드 포인터가 필요 없고,
오른쪽 연결 부분에만 스레드를 연결한다. 오른쪽 연결 부분은 직후에 방문할 노드이므로 D를 가리키게 한다.
노드 I의 경우 오른쪽 스레드가 가리킬 직후에 방문될 노드는 없다. → 노드 I의 스레드는 근노드를 가리키게 한다.
(이건 쓸 필요 없고 그냥 참고용)

참고 자료

없음