트리 데이터 구조로 다듬기

다음은 이진 검색 트리(BST)입니다. 모든 원을 노드라고 하며 각 노드는 2개의 다른 노드(왼쪽과 오른쪽에 하나씩)에 연결될 수 있습니다. 이것이 이진 트리라고 불리는 이유이며, 2개의 "하위"노드가 있고 트리처럼 보입니다!



왼쪽 자식 노드는 항상 부모 노드보다 값이 작거나 같고 오른쪽 자식 노드는 항상 크거나 같습니다. 일부 구현에서는 왼쪽 또는 오른쪽 노드만 부모와 같을 수 있습니다. 개인적으로 같은 노드를 왼쪽에 배치하는 것을 좋아합니다 😁

BTW, 여기 python3을 사용하는 이진 검색 트리가 있습니다!

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

왼쪽 및 오른쪽 트리의 기본값은 null/None이고 기본값은 0입니다.

순회

각 순회에 대해 루트(맨 위)에서 시작하여 이진 트리를 통해 이동하는 방법에 대해 간략하게 설명하겠습니다. 그런 다음 Python을 사용하여 순회 코드를 보여주고 마지막으로 프로그램이 트리를 통해 이동하는 방법을 시각화하는 GIF를 보여줍니다! 또한 gif 크기가 너무 커져서 짧게 잘라야 했기 때문에 전체 트리를 거치지 않고 모든 gif가 일찍 종료됩니다 🤷‍♂️.

처음 3개는 매우 유사하고 한 줄의 코드만 다르지만 매우 다른 결과를 제공합니다! 나는 그것들을 순회 삼중체라고 부릅니다.

순서대로

이 메서드는 트리를 "순서대로"이동합니다. 모든 노드의 값을 가장 작은 것부터 가장 큰 순서로 인쇄한다는 의미입니다.

재귀를 사용하여 함수는 왼쪽 하위 트리에서 자신을 호출한 다음 현재 값을 인쇄한 다음 오른쪽 하위 트리에서 자신을 호출합니다.
결과는 트리의 값을 .... 순서대로 인쇄한다는 것입니다.

def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(node.val)
    in_order(node.right)

깊이 우선 검색(선주문이라고도 함)

깊이 우선 검색은 트리 및 그래프에 대한 고전적인 순회 방법입니다. 이 방법은 현재 노드에서 먼저 작동한 다음 왼쪽 및 오른쪽 자식 노드에서 작동하기 때문에 선주문 순회라고도 합니다.

깊이 우선 탐색은 일반 순회 및 트리 복사에 매우 인기가 있습니다.

def dfs(node):
    if node == None:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)

주문 후

순회 삼중 항의 마지막. 먼저 왼쪽 및 오른쪽 자식 노드에서 작동한 다음 현재 노드에서 작동합니다.

Post Order는 아래에서 위로 이동하므로 트리를 삭제하는 데 매우 유용합니다.

def post_order(node):
    if node == None:
        return
    post_order(node.left)
    post_order(node.right)
    print(node.val)

너비 우선 검색(레벨 순서)

이것은 조금 더 까다로우며 대기열을 통해서만 수행할 수 있습니다. 재귀로 가능할 수도 있지만 반복적으로 이해하는 것이 더 쉽습니다. 트래버스할 때 대기열을 사용하므로 노드가 추가될 때 트리를 통과합니다. 결과적으로 트리를 한 단계씩 통과합니다. 이것은 너비 우선 검색을 그래프에서도 널리 사용되는 검색 알고리즘으로 만듭니다.

애니메이션을 만들 수는 없지만 노드가 인쇄되는 순서를 보여주기 위해 번호가 매겨진 다이어그램을 만들었습니다!

# deque is a python queue library
from collections import deque

def bfs(root):
    q = deque([root])
    while len(q) > 0:
        node = q.popleft()
        print(node.val)
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

결론

이 4가지 순회 방법을 이해하면 이진 트리와 관련된 대부분의 인터뷰 문제를 이해할 수 있습니다. 사용할 올바른 순회 방법을 알고 있다면 많은 문제를 쉽게 해결할 수 있는 덩어리로 나눌 수 있습니다! 정확한 방법론이 궁금하시다면 곧 가이드를 들고 왔어요! 이진 트리 문제를 해결하는 데 필요한 유일한 리소스가 되기를 바랍니다.

또한 모든 애니메이션은 http://btv.melezinek.cz/binary-search-tree.html에서 제공되었습니다. 애니메이션을 가지고 놀고 싶다면 확인하십시오!

그건 그렇고, 나는 가이드를 만들고 있습니다

저는 LeetCode에서(따라서 인터뷰에서) 거의 모든 이진 트리 문제를 해결하는 방법에 대한 가이드를 만들고 있습니다! 내 여정에 함께 하세요

여기 살짝 엿보기😃









압디살란 모하무드










아이디어: LeetCode에서 141개의 이진 트리 질문을 모두 해결한 다음 해결 방법에 대한 가이드를 게시하겠습니다. 지금까지 141개 중 18개를 완료했습니다. 왜? 솔직히 어떤 것이든 내 다음 직업 사냥을 위한 좋은 메모가 될 것입니다.


오후 19:30 - 2020년 8월 30일





0

5