반응형
스레드 트리
- 정해진 순회 방법에 따라 방문 순서를 유지하는 스레드라는 포인터를 사용 (스레드 포인터를 갖는 이진트리)
- 스레드는 오른쪽(노드의 후속 노드) / 왼쪽(노드의 선행 노드) 두가지가 있다
- 스레드 없이 순회를 그냥 하게되면 스택에 저장해서 관리해야하는 번거로움이 발생해서 사용하기 시작되었다
- 전위 순회, 중위 순회 , 후위 순회
2. 스레드 트리 구현
struct TNode {
int info; // 데이터
TNode left; // 왼쪽 자식 포인터
TNode right; // 오른쪽 자식 포인터
TNode right_thread; // 왼쪽 스레드 포인터
TNode left_thread; // 오른쪽 스레드 포인터
}
- 중위 순회 연산
// 루트를 가리키는 포인터(firstin)을 매개벼수로 받는다
void inorder(struct TNode *firstin){
struct TNode *p; // 포인터 p를 만들고,
p = firstin; // 루트노드를 가리킨다
while (p != NULL){ // 루트가 있으면
printf("%d", p → info); // p의 데이터를 출력
p = p → right_thread; // p를 오른쪽 스레드로 변경
}
}
그런데 이렇게 했더니 비는 포인터들이 너무 많아진다 (메모리 낭비)
→ 그래서 포인터가 null 인 친구들만 스레드 노드 값을 넣어주면 빈포인터를 활용할 수 있다
(플래그를 추가해서 자식포인터이면 0, 스레드이면 1)
class TFNode {
int info; // 데이터
int threadFlag; // 자식인지 스레드인지 알려주는 flag
TFNode left; // 왼쪽 포인터
TFNode right; // 오른쪽 포인터
}
이렇게 되면 자연스럽게 자식포인터 따라가다가 포인터가 비게되면
스레드로 대체되서 따라간다. 자연스러운 흐름이 만들어진다
**null 포인터의 개수 구하기
노드가 n 개인 이진트리를 연결리스트로 구현할 때 2n-(n-1) = n + 1;
3. 스레드 트리 순회
다음은 전위순회함수이다
(단순하게 트리를 순회할 때는 threadFlag 를 사용하지 않는다)
- 스레드 트리 전위 순회
// root를 매개변수로 받는다
void Preorder(struct TFNode *root){
struct TFNode *p; // 포인터 p를 선언
p = root; // 루트 노드를 넣어준다
while(p != NULL){ // 루트가 값이 있으면
print("%d", p → info); // 데이터 출력하고
p = p → left; // 루트를 왼쪽 서브트리로 하나씩 내린다
}
}
- 스레드 트리 노드 삽입
struct TNode {
int info; // 데이터
TNode left; // 왼쪽 자식 포인터
TNode right;// 오른쪽 자식 포인터
TNode right_thread; // 왼쪽 스레드 포인터
TNode left_thread; // 오른쪽 스레드 포인터
}
// 매개변수를 노드prev(직전 노드)와 노드new(삽입할 노드)
void Insert(struct TNode *prev, struct TNode *new){
new → left = NULL; // new노드의 왼쪽 포인터를 null
new → right = prev → right; // new노드의 오른쪽 포인터를 prev노드의 오른쪽으로
new → left_thread = prev; // new노드의 오른쪽 스레드를 x로 지정
new → right_thread = prev → right_thread; // new노드의 오른쪽 스레드를 prev의 오른쪽 스레드로 지정
prev → right = new; // prev의 오른쪽은 new노드 값으로
prev → right_thread = new; // prev의 오른쪽 스레드 값도 new 노드 값으로
}
**삭제의 경우 훨씬 복잡하고 까다롭다
1) 삭제한 노드의 모든 자식 삭제 → 내부노드를 수시로 삭제해야 한다면 스레드를 포기할수도...
2) 삭제한 노드의 서브트리의 루트를 삭제한 노드의 원래 자리로 이동
3) 잎만 삭제
반응형
'OS & Network' 카테고리의 다른 글
Network - HTTP 살펴보기(2) (Method / Status Code) (0) | 2024.01.18 |
---|---|
Network - HTTP 살펴보기 (1) (Request / Response / Header) (1) | 2023.12.07 |
자료구조 - 트리란 (1) | 2023.12.03 |
자료구조 - 연결리스트의 응용 (3) | 2023.12.01 |
자료구조 - 연결 리스트란 (1) | 2023.11.29 |
댓글