[ 자료구조 ] 이진 트리 (binary tree)

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 이동
• 왼쪽 서브 트리와 오른쪽 서브 트리도 똑같이 구성
• 모든 노드 값은 중복되지 않는다.