Ch08 Lab - 트리

📘 교재 예제 (Code)

📘 Textbook Examples (Code)

Code08-01.py

이진 트리 노드를 수동으로 생성하고 연결합니다

class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

node1 = TreeNode()
node1.data = '화사'

node2 = TreeNode()
node2.data = '솔라'
node1.left = node2

node3 = TreeNode()
node3.data = '문별'
node1.right = node3

node4 = TreeNode()
node4.data = '휘인'
node2.left = node4

node5 = TreeNode()
node5.data = '쯔위'
node2.right = node5

node6 = TreeNode()
node6.data = '선미'
node3.left = node6

print(node1.data, end = ' ')
print()
print(node1.left.data,  node1.right.data, end = ' ')
print()
print(node1.left.left.data, node1.left.right.data, node1.right.left.data, end = ' ')

Code08-01.py

Manually creates and connects binary tree nodes

class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

node1 = TreeNode()
node1.data = 'Hwasa'

node2 = TreeNode()
node2.data = 'Solar'
node1.left = node2

node3 = TreeNode()
node3.data = 'Moonbyul'
node1.right = node3

node4 = TreeNode()
node4.data = 'Wheein'
node2.left = node4

node5 = TreeNode()
node5.data = 'Tzuyu'
node2.right = node5

node6 = TreeNode()
node6.data = 'Sunmi'
node3.left = node6

print(node1.data, end = ' ')
print()
print(node1.left.data,  node1.right.data, end = ' ')
print()
print(node1.left.left.data, node1.left.right.data, node1.right.left.data, end = ' ')

Code08-02.py

이진 트리를 순회합니다 (전위/중위/후위)

class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

node1 = TreeNode()
node1.data = '화사'

node2 = TreeNode()
node2.data = '솔라'
node1.left = node2

node3 = TreeNode()
node3.data = '문별'
node1.right = node3

node4 = TreeNode()
node4.data = '휘인'
node2.left = node4

node5 = TreeNode()
node5.data = '쯔위'
node2.right = node5

node6 = TreeNode()
node6.data = '선미'
node3.left = node6

def preorder(node) :

	if node == None:
		return
	print(node.data, end='->')
	preorder(node.left)
	preorder(node.right)

def inorder(node):

	if node == None :
		return
	inorder(node.left)
	print(node.data, end='->')
	inorder(node.right)

def postorder(node):

	if node == None :
		return
	postorder(node.left)
	postorder(node.right)
	print(node.data, end='->')

print('전위 순회 : ', end = '')
preorder(node1)
print('끝')

print('중위 순회 : ', end = '')
inorder(node1)
print('끝')

print('후위 순회 : ', end = '')
postorder(node1)
print('끝')

Code08-02.py

Traverses a binary tree (preorder/inorder/postorder)

class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

node1 = TreeNode()
node1.data = 'Hwasa'

node2 = TreeNode()
node2.data = 'Solar'
node1.left = node2

node3 = TreeNode()
node3.data = 'Moonbyul'
node1.right = node3

node4 = TreeNode()
node4.data = 'Wheein'
node2.left = node4

node5 = TreeNode()
node5.data = 'Tzuyu'
node2.right = node5

node6 = TreeNode()
node6.data = 'Sunmi'
node3.left = node6

def preorder(node) :

	if node == None:
		return
	print(node.data, end='->')
	preorder(node.left)
	preorder(node.right)

def inorder(node):

	if node == None :
		return
	inorder(node.left)
	print(node.data, end='->')
	inorder(node.right)

def postorder(node):

	if node == None :
		return
	postorder(node.left)
	postorder(node.right)
	print(node.data, end='->')

print('Preorder traversal: ', end = '')
preorder(node1)
print('End')

print('Inorder traversal: ', end = '')
inorder(node1)
print('End')

print('Postorder traversal: ', end = '')
postorder(node1)
print('End')

Code08-03.py

이진 탐색 트리에 데이터를 삽입합니다

## 함수 선언 부분 ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크',  '걸스데이', '트와이스' ]

## 메인 코드 부분 ##

node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

print("이진 탐색 트리 구성 완료!")

Code08-03.py

Inserts data into a binary search tree

## Function Declarations ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## Global Variables ##
memory = []
root = None
nameAry = ['BlackPink', 'RedVelvet', 'Mamamoo', 'Apink',  'GirlsDay', 'TWICE' ]

## Main Code ##
node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

print("BST construction complete!")

Code08-04.py

이진 탐색 트리에서 데이터를 검색합니다

## 함수 선언 부분 ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크',  '걸스데이', '트와이스' ]

## 메인 코드 부분 ##

node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

findName = '마마무'

current = root
while True :
	if findName == current.data:
		print(findName, '을(를) 찾음.')
		break
	elif findName < current.data :
		if current.left == None :
			print(findName, '이(가) 트리에 없음')
			break
		current = current.left
	else :
		if current.right == None :
			print(findName, '이(가) 트리에 없음')
			break
		current = current.right

Code08-04.py

Searches for data in a binary search tree

## Function Declarations ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## Global Variables ##
memory = []
root = None
nameAry = ['BlackPink', 'RedVelvet', 'Mamamoo', 'Apink',  'GirlsDay', 'TWICE' ]

## Main Code ##
node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

findName = 'Mamamoo'

current = root
while True :
	if findName == current.data:
		print(findName, ' found.')
		break
	elif findName < current.data :
		if current.left == None :
			print(findName, ' not in tree')
			break
		current = current.left
	else :
		if current.right == None :
			print(findName, ' not in tree')
			break
		current = current.right

Code08-05.py

이진 탐색 트리에서 노드를 삭제합니다

## 함수 선언 부분 ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## 전역 변수 선언 부분 ##
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크',  '걸스데이', '트와이스' ]

## 메인 코드 부분 ##

node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

deleteName = '마마무' 

current = root
parent = None
while True:
	if deleteName == current.data :
		
		if current.left == None and current.right == None : 
			if parent.left == current :
				parent.left = None
			else :
				parent.right = None
			del(current)

		elif current.left != None and current.right == None : 
			if parent.left == current :
				parent.left = current.left
			else :
				parent.right = current.left
			del(current)

		elif current.left == None and current.right != None : 
			if parent.left == current:
				parent.left = current.right
			else:
				parent.right = current.right
			del(current)

		print(deleteName, '이(가) 삭제됨.')
		break
	elif deleteName < current.data :
		if current.left == None :
			print(deleteName, '이(가) 트리에 없음')
			break
		parent = current
		current = current.left
	else:
		if current.right == None :
			print(deleteName, '이(가) 트리에 없음')
			break
		parent = current
		current = current.right

Code08-05.py

Deletes a node from a binary search tree

## Function Declarations ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## Global Variables ##
memory = []
root = None
nameAry = ['BlackPink', 'RedVelvet', 'Mamamoo', 'Apink',  'GirlsDay', 'TWICE' ]

## Main Code ##
node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

deleteName = 'Mamamoo' 

current = root
parent = None
while True:
	if deleteName == current.data :
		
		if current.left == None and current.right == None : 
			if parent.left == current :
				parent.left = None
			else :
				parent.right = None
			del(current)

		elif current.left != None and current.right == None : 
			if parent.left == current :
				parent.left = current.left
			else :
				parent.right = current.left
			del(current)

		elif current.left == None and current.right != None : 
			if parent.left == current:
				parent.left = current.right
			else:
				parent.right = current.right
			del(current)

		print(deleteName, ' deleted.')
		break
	elif deleteName < current.data :
		if current.left == None :
			print(deleteName, ' not in tree')
			break
		parent = current
		current = current.left
	else:
		if current.right == None :
			print(deleteName, ' not in tree')
			break
		parent = current
		current = current.right

Code08-06.py

랜덤 데이터로 이진 탐색 트리를 생성하고 검색합니다

import random
## 함수 선언 부분 ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## 전역 변수 선언 부분 ##
memory = []
rootBook, rootAuth = None, None
bookAry = [ ['어린왕자', '쌩떽쥐베리'],['이방인', '까뮈'], ['부활', '톨스토이'],
		   ['신곡', '단테'], ['돈키호테', '세브반테스'], ['동물농장', '조지오웰'],
		   ['데미안','헤르만헤세'], ['파우스트', '괴테'], ['대지', '펄벅'] ]
random.shuffle(bookAry)

## 메인 코드 부분 ##

### 책 이름 트리 ###

node = TreeNode()
node.data = bookAry[0][0]
rootBook = node
memory.append(node)

for book in bookAry[1:] :
	name = book[0]
	node = TreeNode()
	node.data = name

	current = rootBook
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

print("책 이름 트리 구성 완료!")

### 작가 이름 트리 ###
node = TreeNode()
node.data = bookAry[0][1]
rootAuth = node
memory.append(node)

for book in bookAry[1:] :
	name = book[1]
	node = TreeNode()
	node.data = name

	current = rootAuth
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

print("작가 이름 트리 구성 완료!")

## 책 이름 및 작가 이름 검색 ##
bookOrAuth = int(input('책검색(1), 작가검색(2)-->'))
findName = input('검색할 책 또는 작가-->')

if bookOrAuth == 1 :
	root = rootBook
else :
	root = rootAuth

current = root
while True:
	if findName == current.data :
		print(findName, '을(를) 찾음.')
		findYN = True
		break
	elif findName < current.data :
		if current.left == None :
			print(findName, '이(가) 목록에 없음')
			break
		current = current.left
	else:
		if current.right == None :
			print(findName, '이(가) 목록에 없음')
			break
		current = current.right

Code08-06.py

Creates a BST with random data and searches it

import random
## Function Declarations ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## Global Variables ##
memory = []
rootBook, rootAuth = None, None
bookAry = [ ['LittlePrince', 'SaintExupery'],['TheStranger', 'Camus'], ['Resurrection', 'Tolstoy'],
		   ['new song', 'Dante'], ['DonQuixote', 'Cervantes'], ['AnimalFarm', 'GeorgeOrwell'],
		   ['Demian','HermannHesse'], ['Faust', 'Goethe'], ['TheGoodEarth', 'PearlBuck'] ]
random.shuffle(bookAry)

## Main Code ##

### Book title tree ###
node = TreeNode()
node.data = bookAry[0][0]
rootBook = node
memory.append(node)

for book in bookAry[1:] :
	name = book[0]
	node = TreeNode()
	node.data = name

	current = rootBook
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

print("Book title tree complete!")

### Author name tree ###
node = TreeNode()
node.data = bookAry[0][1]
rootAuth = node
memory.append(node)

for book in bookAry[1:] :
	name = book[1]
	node = TreeNode()
	node.data = name

	current = rootAuth
	while True :
		if name < current.data :
			if current.left == None :
				current.left = node
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				break
			current = current.right

	memory.append(node)

print("Author name tree complete!")

## Search book and author names ##
bookOrAuth = int(input('Book search(1), Author search(2)-->'))
findName = input('Book or author to search-->')

if bookOrAuth == 1 :
	root = rootBook
else :
	root = rootAuth

current = root
while True:
	if findName == current.data :
		print(findName, ' found.')
		findYN = True
		break
	elif findName < current.data :
		if current.left == None :
			print(findName, ' not in list')
			break
		current = current.left
	else:
		if current.right == None :
			print(findName, ' not in list')
			break
		current = current.right

📗 응용 예제 (Ex)

📗 Applied Examples (Ex)

Ex08-01.py

이진 탐색 트리 응용: 랜덤 데이터 삽입/삭제/검색

import random
## 함수 선언 부분 ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## 전역 변수 선언 부분 ##
memory = []
root = None
dataAry = ['바나나맛우유', '레쓰비캔커피', '츄파춥스', '도시락',  '삼다수', '코카콜라' ,'삼각김밥']
sellAry = [ random.choice(dataAry) for _ in  range(20)]

print('오늘 판매된 물건(중복O) -->', sellAry)

## 메인 코드 부분 ##

node = TreeNode()
node.data = sellAry[0]
root = node
memory.append(node)

for name in sellAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name == current.data :
			break
		if name < current.data :
			if current.left == None :
				current.left = node
				memory.append(node)
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				memory.append(node)
				break
			current = current.right

print("이진 탐색 트리 구성 완료!")

def preorder(node) :
	if node == None :
		return
	print(node.data, end = ' ')
	preorder(node.left)
	preorder(node.right)

print('오늘 판매된 종류(중복X)--> ', end = ' ')
preorder(root)

Ex08-01.py

BST application: insert, delete, and search random data

import random
## Function Declarations ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## Global Variables ##
memory = []
root = None
dataAry = ['BananaMilk', 'LetsBeCoffee', 'ChupaChups', 'Lunchbox',  'Samdasu', 'CocaCola' ,'Onigiri']
sellAry = [ random.choice(dataAry) for _ in  range(20)]

print('Items sold today (with duplicates) -->', sellAry)

## Main Code ##
node = TreeNode()
node.data = sellAry[0]
root = node
memory.append(node)

for name in sellAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name == current.data :
			break
		if name < current.data :
			if current.left == None :
				current.left = node
				memory.append(node)
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				memory.append(node)
				break
			current = current.right

print("BST construction complete!")

def preorder(node) :

	if node == None :
		return
	print(node.data, end = ' ')
	preorder(node.left)
	preorder(node.right)

print('Types sold today (no duplicates)--> ', end = ' ')
preorder(root)

Ex08-02.py

이진 탐색 트리 응용: 폴더 구조를 트리로 표현

import os
## 함수 선언 부분 ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## 전역 변수 선언 부분 ##
memory = []
root = None
fnameAry = []

## 메인 코드 부분 ##

folderName = 'C:/Program Files/Common Files/'
for dirName, subDirList, fnames in os.walk(folderName) :
	for fname in fnames :
		fnameAry.append(fname)

node = TreeNode()
node.data = fnameAry[0]
root = node
memory.append(node)

dupNameAry = []

for name in fnameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name == current.data :
			dupNameAry.append(name)
			break
		if name < current.data :
			if current.left == None :
				current.left = node
				memory.append(node)
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				memory.append(node)
				break
			current = current.right

dupNameAry = list(set(dupNameAry))

print(folderName, '및 그 하위 디렉터리의 중복된 파일 목록 -->')
print(dupNameAry)

Ex08-02.py

BST application: represent folder structure as a tree

import os
## Function Declarations ##
class TreeNode() :
	def __init__ (self) :
		self.left = None
		self.data = None
		self.right = None

## Global Variables ##
memory = []
root = None
fnameAry = []

## Main Code ##
folderName = 'C:/Program Files/Common Files/'
for dirName, subDirList, fnames in os.walk(folderName) :
	for fname in fnames :
		fnameAry.append(fname)

node = TreeNode()
node.data = fnameAry[0]
root = node
memory.append(node)

dupNameAry = []

for name in fnameAry[1:] :

	node = TreeNode()
	node.data = name

	current = root
	while True :
		if name == current.data :
			dupNameAry.append(name)
			break
		if name < current.data :
			if current.left == None :
				current.left = node
				memory.append(node)
				break
			current = current.left
		else :
			if current.right == None :
				current.right = node
				memory.append(node)
				break
			current = current.right

dupNameAry = list(set(dupNameAry))

print(folderName, 'and duplicate files in subdirectories -->')
print(dupNameAry)

📙 자가 실습 (Self)

📙 Self Practice (Self)

Self08-01.py

이진 트리를 직접 생성하고 순회합니다

class TreeNode() :
    def __init__ (self) :
        self.left = None
        self.data = None
        self.right = None

node1 = TreeNode()
node1.data = '화사'

node2 = TreeNode()
node2.data = '솔라'
node1.left = node2

node3 = TreeNode()
node3.data = '문별'
node1.right = node3

node4 = TreeNode()
node4.data = '휘인'
node2.left = node4

node5 = TreeNode()
node5.data = '쯔위'
node2.right = node5

node6 = TreeNode()
node6.data = '선미'
node3.left = node6

node7 = TreeNode()
node7.data = '다현'
node4.right = node7

node8 = TreeNode()
node8.data = '사나'
node6.right = node8

def preorder(node):

    if node == None:
        return
    print(node.data, end='->')
    preorder(node.left)
    preorder(node.right)

def inorder(node):

    if node == None:
        return
    inorder(node.left)
    print(node.data, end='->')
    inorder(node.right)

def postorder(node):

    if node == None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end='->')

print('전위 순회 : ', end = '')
preorder(node1)
print('끝')

print('중위 순회 : ', end = '')
inorder(node1)
print('끝')

print('후위 순회 : ', end = '')
postorder(node1)
print('끝')

Self08-01.py

Builds and traverses a binary tree yourself

class TreeNode() :
    def __init__ (self) :
        self.left = None
        self.data = None
        self.right = None

node1 = TreeNode()
node1.data = 'Hwasa'

node2 = TreeNode()
node2.data = 'Solar'
node1.left = node2

node3 = TreeNode()
node3.data = 'Moonbyul'
node1.right = node3

node4 = TreeNode()
node4.data = 'Wheein'
node2.left = node4

node5 = TreeNode()
node5.data = 'Tzuyu'
node2.right = node5

node6 = TreeNode()
node6.data = 'Sunmi'
node3.left = node6

node7 = TreeNode()
node7.data = 'Dahyun'
node4.right = node7

node8 = TreeNode()
node8.data = 'Sana'
node6.right = node8

def preorder(node):

    if node == None:
        return
    print(node.data, end='->')
    preorder(node.left)
    preorder(node.right)

def inorder(node):

    if node == None:
        return
    inorder(node.left)
    print(node.data, end='->')
    inorder(node.right)

def postorder(node):

    if node == None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end='->')

print('Preorder traversal: ', end = '')
preorder(node1)
print('End')

print('Inorder traversal: ', end = '')
inorder(node1)
print('End')

print('Postorder traversal: ', end = '')
postorder(node1)
print('End')

Self08-02.py

이진 탐색 트리의 삽입/검색을 직접 구현합니다

## 함수 선언부
class TreeNode() :
    def __init__ (self) :
        self.left = None
        self.data = None
        self.right = None

## 전역 변수 선언부
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크',  '걸스데이', '트와이스', '잇지',
           '여자친구']

## 메인 코드부

node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)

for name in nameAry[1:] :

    node = TreeNode()
    node.data = name

    current = root
    while True :
        if name < current.data :
            if current.left == None :
                current.left = node
                break
            current = current.left
        else :
            if current.right == None:
                current.right = node
                break
            current = current.right

    memory.append(node)


findName = input('찾을 그룹이름-->')

current = root
while True:
    if findName == current.data:
        print(findName, '을(를) 찾았음.')
        break
    elif findName < current.data :
        if current.left == None :
            print(findName, '이(가) 트리에 없음')
            break
        current = current.left
    else:
        if current.right == None :
            print(findName, '이(가) 트리에 없음')
            break
        current = current.right