이 글은 기존 Tistory 블로그에서 옮겨온 글입니다. 원문: https://jms3084.tistory.com/14
1. 주어진 리스트로 이진 트리 생성 (중복 제거)
def generate_book_tree(bookAry):
node = TreeNode()
node.data = bookAry[0][0]
root = node
for i in bookAry[1:]:
node = TreeNode()
node.data= i[0]
current = root
while True:
if current.data > i[0]:
if current.left ==None:
current.left = node
break
current = current.left
elif current.data < i[0]:
if current.right ==None:
current.right = node
break
current = current.right
else:
pass
return root
2. 이진 탐색 트리 데이터 검색
def find_node(root, findName):
current = root
while True:
if current.data == findName:
result = findName + '을(를) 찾음.'
break
elif current.data > findName:
if current.left == None:
result = findName + '이(가) 트리에 없음'
break
current = current.left
else:
if current.right == None:
result = findName + '이(가) 트리에 없음'
break
current = current.right
return result
3. 전위 순회
def preorder(node):
if node ==None:
return
print(node.data, end = ' ')
preorder(node.left)
preorder(node.right)
4. 중위 순회
def inorder(node):
if node ==None:
return
inorder(node.left)
print(node.data, end = ' ')
inorder(node.right)
5. 후위 순회
def postorder(node):
if node ==None:
return
postorder(node.left)
postorder(node.right)
print(node.data, end = ' ')
6. root 받아 left, right 반전 후 root 반환 함수
def invertTree(root):
if root==None:
return
root.right, root.left = root.left, root.right
invertTree(root.left)
invertTree(root.right)
return root
7. 큰 값부터 작은 값으로 순회, 배열 누적 함수
def traverse_node(root, result):
if root == None:
return
traverse_node(root.right, result)
result.append(root.data)
traverse_node(root.left, result)
return result
8. 이진 탐색 트리의 원리
- 연결리스트의 head노드가 이진 트리에서는 root노드로 표현된다.
- root노드의 data보다 작은 값이 들어오면 left, 큰 값이 들어오면 right 이동
- 왼쪽 서브 트리와 오른쪽 서브 트리도 똑같이 구성
- 모든 노드 값은 중복되지 않는다.