[알고리즘, 자료구조] Tree 트리

1. 트리란?

Tree는 비선형 자료구조로 서로 연결된 Node의 계층형 자료구조이다. root와 부모-자식 관계의 subtree로 구성되어 있다

 

2. 트리의 개념

3. 트리 구현

class Node:
    def __init__(self, value = 0, left = None, right  = None) :
        self.value = value
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self):
        self.root = None

bt = BinaryTree()
bt.root = Node(value=1)
bt.root.left = Node(value=2)
bt.root.right = Node(value=3)
bt.root.left.left = Node(value=4)
bt.root.left.right = Node(value=5)
bt.root.right.right = Node(value=6)

1. Level order traversal

- level 별로 순회하는 것

from collections import deque

def levelOrder(root):
    visited = []
    if root in None:
        return 0
    q = deque()
    q.append(root)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

2. preorder traversal

<preorder>

# 전위순회
def preorder(cur_node):
    if cur_node is None:
        return 
    print(cur_node.value)
    preorder(cur_node.left)
    preorder(cur_node.right)

3. inorder traversal

<inorder>

# 중위순회
def inorder(cur_node):
    if cur_node is None:
        return
    inorder(cur_node.left)
    print(cur_node.value)
    inorder(cur_node.right)

4. postorder traversal

<postorder>

# 후위순회
def postorder(cur_node):
    if cur_node is None:
        return
    postorder(cur_node.left)
    postorder(cur_node.right)
    print(cur_node.value)