이진트리

표현법

1. 배열, 리스트

마치 heap 으로 구현했던 것 처럼 구현 할 수 있다.
하지만 이는 메모리의 낭비를 초래 할 수 있다.

2. 노드와 링크 직접 구현

Node 클래스와 Tree 클래스를 이용해서 구현 할 수 있다.

class Node:

  def __init__(self,  key):
    self.key = key 
    self.parent = self.left = self.right = None

  def __str__(self):
    return str(self.key)

Node 는 노드의 값을 나타내는 key 값과 링크 된 노드들을 가리키는 left ,right, parent 를 값으로 갖는다.

순회 (traversal)

이진트리 노드의 key 값을 빠짐없이 출력하는 방법

순회 할 때 루트노드와 좌측, 우측 트리 어떤 순서로 순회 할 것인지에 따라 다르다.

순회 하는 것은 재귀 함수를 통해 구현 할 수 있다.

class Node:

  def __init__(self,  key):
    self.key = key 
    self.parent = self.left = self.right = None

  def __str__(self):
    return str(self.key)
  
  def preorder(self):
    if self != None:
      print(self.key)
      if self.left:
        self.left.preorder()
      if self.right:
        self.right.preorder()

  def inorder(self):
    if self != None:
      if self.left:
        self.left.inorder()
      print(self.key)
      if self.right:
        self.right.inorder()

  def postorder(self):
    if self != None:
      if self.left:
        self.left.postorder()
      if self.right:
        self.right.postorder()
      print(self.key)

preorder , inorder , postorder 모두 key != none일 때 까지 반복된다. 그러니 끝 까지 순회한다.

모든 순회 방식 모두 로직이 같으나 subtree 들에 대해서 root node 를 언제 프린트 하냐만 다른 방식이다.