[자료구조] 트리

 

 

계층적 자료구조(트리 / 수직적) ↔ 선형적 자료구조(배열, 링크드리스트 / 수평적)

 

링크드리스트와 같이 노드에 값을 저장(하위관계 가르키는 레퍼런스를 갖음)

자식노드를 화살표로 가르킴

root노드로부터 시작(하위 어디든갈 수 있음)

 

트리의 활용 : 다양한 추상자료형 구현가능

 

이진트리 만들기 

0. 노드클래스 생성 

class Node:
    """이진 트리 노드 클래스"""
    def __init__(self, data):
            self.data = data
            self.left_child = None
            self.right_child = None

 

1. 노드인스턴스 생성(root / 그 이외) 👉 root_node = Node("A")

2. 노드인스턴스 연결(root부터 left/right 나누어서 모두 언급해준다)

# 노드 인스턴스들 연결
root_node.left_child = node_B
root_node.right_child = node_C

node_B.left_child = node_D
node_B.right_child = node_E

node_C.right_child = node_F

node_E.left_child = node_G
node_E.right_child = node_H

여기까지 해서 트리가 만들어지면

3. 원하는 코드로 값을 찾아낸다

# 실행 코드
test_node = root_node.right_child.right_child
print(test_node.data)

 

 

완전이진트리(full binary tree)에서 자식노드 찾아가기

1. 왼쪽 자식 찾고싶을때 : 부모노드의 인덱스 * 2

2. 오른쪽 자식 찾고싶을때 : 부모노드 인덱스 * 2 + 1

 

완전이진트리(full binary tree)에서 부모노드 찾아가기

1. 왼쪽 자식의 부모노드 : 인덱스 / 2

2. 오른쪽 자식의 부모노드 : 인덱스 / 2에서 정수값만 가져오기

 

👉완전이진트리에서만 적용가능한 계산법 : 마지막 레벨의 전레벨에서는 모든 트리가 가득 차 있기때문에