18강 요약

이진 트리는, 트리에 포함되는 모든 노드의 차수가 2 이하인 트리를 말합니다. 즉, 모든 노드는 자식이 없거나 (리프 노드의 경우), 하나만 있거나, 아니면 둘 있는 세 경우 중 하나에 해당합니다. 해당 노드의 노드수, 깊이를 출려해보고 순서에 따른 트리의 순회를 해봅니다.

18강 내용

트리의 노드 수

size() - 현재 트리에 포함되어 있는 노드의 수를 구함

class Node:
	def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

class BinaryTree:
	def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0

트리의 높이

depth() - 현재 트리의 깊이 (또는 높이) 를 구함

class Node:
	def deth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return l + 1 if l >= r else r + 1
      
class BinaryTree:
	def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

트리의 순회

중위 순회

중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회

class Node:
	def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal
  
class BinaryTree:
	def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

전위 순회

전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회

class Node:
	def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
        
class BinaryTree:
	def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

후위 순회

후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문

class Node:
	def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        traversal.append(self.data)
        return traversal
        
class BinaryTree:
	def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

전체 코드

class Node:
    def __init__(self,item):
        self.data = item
        self.left = None
        self.right = None

    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

    def deth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return l + 1 if l >= r else r + 1
        
    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal

    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal

    def postorder(self):
        traversal = []
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        traversal.append(self.data)
        return traversal

class BinaryTree:
    def __init__(self,r):
        self.root = r

    
    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0
    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0

    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
    
    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

GitHub

https://github.com/ds02168/Study_Algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/18%EA%B0%95/18%EA%B0%95.py