👩🏼‍💻TIL : 11. 🎄🎄트리🎄🎄

00. 트리?

  ① 데이터가 상/하 관계 또는 계층적 관계를 저장할 수 있는 자료구조

  ② 컴퓨터 과학의 다양한 문제를 해결할 수 있음(정렬 / 압축)

  ③ 여러 추상 자료형을 구현 할 수 있음

  

01. 트리 용어

  ① root노드(뿌리 노드) : 트리의 시작 노드, 뿌리가 되는 노드를 말한다.

  ② 부모 노드 : 특정 노드의 직속 상위 노드

  ③ 자식 노드 : 특정 노드의 직속 하위 노드

  ④ 형제 노드 : 같은 부모를 갖는 노드

  ⑤ leaf 노드 : 잎 / 말단 노드 트리의 끝에 있다고 해서 root과 반대되는 표현 leaf라고 불린다. 

   

 

01. 이진트리 : 이진 트리란 각 노드가 최대 2개의 노드를가질 수 있는 트리이다.

   (1) 완전 이진 트리가 가지는 성질

      ① 마지막 레벨 - 1 까지는 노드들로 가득 차 있다.

      ② 마지막 레벨은 왼쪽에서 오른쪽 방향으로 노드들로 가득 차 있어야 한다. 

   (1) 자식 노드를 찾아보자 : 이진트리에서 특정 부모노드의 왼쪽 자식을 찾고 싶을 때는 부모노드가 저장된 인덱스에 2를 곱해준 인덱스로 생각하고 리스트에서 찾자. 오른쪽은 부모노드의 인덱스 곱하기 2 + 1을 해주면 오른쪽 자식의 인덱스를 찾을 수 있다. 

   (2) 부모 노드 찾기 : 자식 노드의 인덱스에서 2를 나누자

#간단한 이진트리를 만들자
Class Node:
	def __init__(self, data):
    	self.data = data
        self.left_child = None
		self.right_child = None

#root노드 생성
root_node = Node("A")
node_B = Node("B")
node_C = Node("C")

root_node.left_child = node_B
root_node.right_child = node_C

#이진트리 리스트에 저장하기
complete_binary_tree = [None, 1, 5, 12, 11, 9 , 10, 14, 2, 10]

 

02. 트리순회  

  ① 재귀적으로 왼쪽 부분 트리순회

  ② 재귀적으로 오른쪽 부분 트리순회

  ③ 현재 노드 데이터를 출력한다. 

 

 (1) pre-order 순회

  ① 현재 노드 데이터를 출력한다. 

  ② 재귀적으로 왼쪽 부분 트리순회

  ③ 재귀적으로 오른쪽 부분 트리순회

   

(2) post-order 순회 

  ① 재귀적으로 왼쪽 부분 트리순회

  ② 재귀적으로 오른쪽 부분 트리순회

  ③ 현재 노드 데이터를 출력한다. 

 

(3) in-order 순회 

  ① 재귀적으로 왼쪽 부분 트리순회

  ② 현재 노드 데이터를 출력한다.  

  ③ 재귀적으로 오른쪽 부분 트리순회