[자료구조] 7. 이진트리 구현, 데이터 순회

 

 

완전 이진트리 → 왼쪽부터 꽉꽉 차있기 때문에 “인덱스”를 통한 동적 할당이 가능함… (힙.. )‘

경사 이진트리 → 중간중간에 듬성듬성 빈 칸이 많이 생겨서 인덱스를 통한 동적 할당으로의 구현이 어려움

→ 그럼 이진 트리 구현 어떻게 하느냐?

 

“양방향 linked list”를 통한 구현

class node:
	def __init__(self, data, prev, next):
		self.data = data
		self.prev = prev
		self.next = next
	
	def insert(value, position):
		new_node = node(value, position, position.next)
		new_node.prev.next = new_node
		new_node.next.prev = new_node
		return new_node      
	
	def delete(target):
		target.prev.next = target.next
		target.next.prev = target.prev
		
	
	def visit_all(start_node):
		now_node = start_node
		while(True):
			print(now_node.data)
			now_node = now_node.next
			if (now_node.data == None):
				break

prev = 왼쪽 자식 노드

next = 오른쪽 자식 노드

자식 노드가 없다면 = None

---

레벨 순회

동일한 깊이를 가지는 노드를 좌측부터 차례로 방문하고, 모두 순회한 경우, 아래로 한 단계씩 내려가는 방식

→ 선입선출의 구조로 큐를 이용하여 구현함

[최전방 출력 → 최전방 자식 enqueue → 최전방 dequeue (출력 x) ]

 

 

 

 

 

 

 

 

 

 

참고

파이썬과 함께하는 자료구조의 이해 - 예스24