[Python] Data Structure - Tree

Tree

그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용됨

 

특징

• 트리는 부모 노드와 자식 노드의 관계로 표현된다
• 트리의 최상단 노드를 루트 노드라고 한다
• 트리의 최하단 노드를 단말 노드라고 한다
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다

Binary Tree

Tree that each node has no more than two child nodes. Each node has a left node and a right node

Binary Search Tree

• 중위 순회(Inorder Traversal)를 하면 키 값의 오름차순으로 노드를 얻을 수 있음
• 이진탐색에 유용
• 노드의 삽입이 쉬움

특징 - 왼쪽 자식 노드<부모노드<오른쪽 자식 노드

 

탐색 구현

(leetcode 993. Cousins in Binary Tree)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def searchNext(self, root: Optional[TreeNode], x, y, depth, parent: Optional[TreeNode]):
        if root == None:
            return
        if root.val == x:
            x_depth = depth
            x_parent = parent
        elif root.val == y:
            y_depth = depth
            y_parent = parent
        else:
            self.searchNext(root.left, x, y, depth+1, root)
            self.searchNext(root.right, x, y, depth+1, root)

1. 루트부터 선택해서 검색을 진행한다. 여기서 선택하는 노드를 p라고 한다.
2. p가 널이면 검색에 실패한다.
3. 검색하는 값 key와 선택한 노드 p와의 키값을 비교하여
    - 값이 같으면 검색에 성공(검색종료)
    - key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입한다.(왼쪽으로 검색 진행)
    - key가 크면 선택한 노드에 오른쪽 자식 노드를 대입한다.(오른쪽으로 검색 진행)
4. 2번 과정으로 되돌아간다.

중위 순회(Inorder Traversal) 구현

• 순회순서 Left -> root -> right

from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution:
    def recursiveInorder(self, root, sol):
        if root:
            self.recursiveInorder(root.left, sol)
            sol.append(root.val)
            self.recursiveInorder(root.right, sol)
        return sol
        
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        sol = []
        if root:
            return self.recursiveInorder(root, sol)

if __name__ == "__main__":
    root = TreeNode(1)
    root.left = None
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    
    sol = Solution()
    result = sol.inorderTraversal(root)
    print(result)

참고

이것이 취업을 위한 코딩 테스트이다

https://sustainable-dev.tistory.com/42