자료구조6 - 트리의 순회와 구현

<트리 순회 - 트리의 노드를 방문하는 순서>

==> DFS(깊이 우선 탐색) /  BFS(너비 우선 탐색)

 

<DFS 깊이 우선 탐색>

1. 전위 순회 

루트 노드부터 시작하여 왼쪽  서브 트리 탐색이 끝난 후 오른쪽 서브 트리로 이동하여 탐색

 

 

2. 중위 순회

맨 왼쪽의 리프노드부터 시작하여 왼쪽 서브 트리 탐색을 끝낸 후, 루트 노드를 들리고 오른쪽 서브 트리로 이동하여 탐색

 

 

 

3. 후위 순회

 

리프노드들부터 시작하여 위쪽으로(루트 노드쪽으로) 점점 이동하여 제일 마지막에 루트 노드를 방문

즉, 아래=> 위로 이동

같은 트리에 대해서는 왼쪽 노드부터 탐색한 후 오른쪽 노드를 방문한다.

해당 구역(?)이 끝났으면 같은 레벨에 있는 오른쪽 트리로 이동하여 탐색 

그리고 맨 마지막에 루트 노드 방문

 

 

DFS는 모두 수직 방향으로 이동하는 것을 알 수 있다.

 

 

 

 

<BFS 너비 우선 탐색>

 

 

루트 노드부터 시작하여 같은 레벨에 있는 것을 왼쪽부터 차례대로 순회한다.

왼=>오 : 가로 방향 이동

 

 

<트리 구현>

class node: 	# 트리를 구성하는 노드(정점) 클래스 
	def__init__(self, data):
		self.data=data
		self.left=None
		self.right=None

class Tree:
	def __init__(self):
		self.root=None	#루트 노드가 아직 없는 상태의 트리로 초기화

완전 이진 트리의 경우, 배열을 이용하여 간단하게 구현이 가능하다.

또, 트리는 그래프의 일종이므로 그래프를 표현할 때 사용하는 인접 행렬, 인접 리스트, 간선 리스트를 사용할 수도 있다.

 

<전위 순회 트리 구현>

1. 현재 노드 

2. 현재 노드의 왼쪽 서브 트리로 이동

3. 현재 노드의 오른쪽 서브 트리로 이동

def preorder(tree):
    result=[]	# 방문한 노드들을 순서대로 담고 있는 리스트
    result.append(tree.index)
    if tree.left != None:	# 왼쪽 트리가 존재한다면
    	result+=preorder(tree.left)	# 왼쪽 서브트리 전위 순회
    if tree.right !=None:	# 오른쪽 트리가 존재한다면
    	result+=preorder(tree.right)	# 오른쪽 서브트리 전위 순회
        
    return result

리스트에 저장을 안하고 순회를 하면서 바로 출력한다면, 더 간단하게 구현가능하다.

def preorder(self, node):
    print(node, end=" ")
    
    if not node.left == None: 
        self.preorder(node.left)
        
    if not node.right==None:
        self.preorder(node.right)

 

<중위 순회 트리 구현>

1. 현재 노드의 왼쪽 서브 트리로 이동

2. 현재 노드 

3. 현재 노드의 오른쪽 서브 트리로 이동

 

def inorder(self, node):
    if not node.left == None:
        self.inorder(node.left)
    
    print(node, end=" ")
    
    if not node.right == None:
        self.inorder(node.right)

 

<후위 순회 트리 구현>

1. 현재 노드의 왼쪽 서브 트리로 이동

2. 현재 노드의 오른쪽 서브 트리로 이동

3. 현재 노드

 

def postorder(self, node):
    if not node.left == None:
        self.postorder(node.left)
        
    if not node.right == None:
        self.postorder(node.right)
        
    print(node, end=" ")

큐는 선입선출이므로 이를 이용하여 BFS를 구현한다.

 

<BFS 순회 트리 구현>

시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문

from queue import Queue

def BFS(tree) :
    q=Queue()
    q.put(tree)     #트리의 루트 노드부터 시작

    result = []

    # 노드와 바로 연결되어 있는 노드부터 순회
    # q에 뭔가 들어있다면 계속 반복을 한다.
    #-> 더 이상 방문할 노드가 없을 때까지 반복문을 돈다.
    while len(q.queue)>0:
        cur = q.get()   # 방뮨할 노드: queue에서 맨 앞에 있는 것부터 빼와서 순회
        if cur == None: # 아무것도 안들어가 있으면
            continue # 그냥 패스해주면됨 (와일문으로 이동)
        
        result.append(cur.index)    # 방문

         # cur와 연결이 되어있는 노드들을 큐에 넣어줌
        q.put(cur.left)  # 선입선출이므로 왼쪽 먼저 넣을 것
        q.put(cur.right)    

    return result

<이진 트리 구현>

class Tree:
    def __init__(self, i, l, r) : #루트 노드
        self.index = i
        self.left = l
        self.right = r

    # 재귀적으로 동작한다.
    # 새로운 노드가 현재 노드의 자식으로 추가되어야 하는 경우 => 바로 추가 
    # 그렇지 않다면, 자기 자식 중에 새로운 노드를 받을 수 있는 노드를 탐색 => 재귀 알고리즘 사용
    def addNode(self, i, l, r) :
        if self.index == None or self.index == i:  # 루트 노드 or 다른 노드의 경우
            self.index = i
            # 왼쪽 노드의 자식 노드는 아직 모름
            # 만약. 들어온 l or r의 값이 None이라면 self.left/right에 None을 넣음
            self.left = Tree(l,None, None) if l !=None else None
            self.right = Tree(r,None, None) if r !=None else None

            return True
        else:
            # 그렇지 않다면, 자기 자식 중에 새로운 노드를 받을 수 있는 노드를 탐색 => 재귀 알고리즘 사용
            flag=False
            if self.left !=None:    # 왼쪽이 유효하면
                flag=self.left.addNode(i, l, r) #왼쪽에 노드 추가
            
            if flag == False and self.right !=None: #위의 코드에서 진행한 왼쪽 노드의 추가가 실패하고 오른쪽이 유효하다면
                flag=self.right.addNode(i, l, r) #오른쪽에 노드 추가
            
            return flag

 

<트리의 높이 구하기>

def getHeight(myTree) :
    # 루트 노드를 기준으로 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이를 모두 구해본다.
    # 왼쪽과 오른쪽 서브트리의 높이 중, 더 큰 높이 +1(루트노드) 가 트리의 높이가 된다.
    if myTree == None:
        return 0
    else:
        return 1 + max(getHeight(myTree.left), getHeight(myTree.right))