이진트리 (Binary Trees)

이진 트리는 트리에 포함되는 모든 노드의 차수가 2 이하인 트리를 말한다. 즉 모든 노드는 자식이 없거나 (리프노드의 경우), 하나만 있거나 아니면 둘 있는 세 경우 중 하나에 해당한다.

 

 

이진 트리의 추상적 자료구조

연산의 정의

• size() - 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() - 현재 트리의 깊이 (또는 높이; height)를 구함
• 순회 (traversal)

 

 

 

이진 트리의 자료구조 구현

# 노드 클래스

# 이진트리의 구현 - 노드(node)
class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None

 

 

 

# 트리 클래스

루트만 알면 된다

# 이진 트리의 구현 - 트리(tree)
class BinaryTree:
    def __init__(self, r):
        self.root = r

 

 

 

# 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()

# 이진트리의 구현 - 노드(node)
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
    
    # depth
    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return max(l,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
        

# 이진 트리의 구현 - 트리(tree)
class BinaryTree:
    # 생성자
    def __init__(self, r):
        self.root = r
        
    # 크기 구하기
    def size(self):
        # 루트가 존재하면 리턴
        if self.root:
            return self.root.size()
        else:
            return 0
        
    # depth
    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 []