자료구조와 알고리즘 - 트리구조2

 

---

 

1. 트리구조의 순회방법

 

1)전위 순회(Preorder): Root를 제일먼저 순회 (Root ->Left -> Right)

( A, B, D, H, E, C, F, G)

2)중위 순회(Inorder): Root를 중간에 순회(Left -> Root -> Right)

(H, D, B, E, A, F, C,G)

3)후위 순회(Posterorder): Root를 제일 나중에 순회(Left -> right -> Right)

(H, D, E, B, F, G, C, A)

4) 레벨 순회(Levelorder) : 위의 레벨부터 순차적으로 탐색(BFS:Breath First Search)

(A, B, C, D, E, F, G, H)

-레벨 순회를 제외한 순회들은 깊이부터 탐색하는 DFS(Depth First Search)이다.

 

-구현

from collections import deque
#기본개념
class Node:
    def __init__(self, data):
        self.data = data
        self.right = None
        self.left = None

a = Node(1)
a.right = Node(2)
a.left = Node(3)



class Bst:
    def __init__(self, data):
        self.root = Node(data)

    def add_(self,data):
        pointer = self.root
        while True:
            if data > pointer.data:      
                if pointer.right == None:     #그 자리가 None이면 바로 대입
                    pointer.right = Node(data)
                    break
                else:                    #아니면 그 자리로 이동
                    pointer = pointer.right 
            elif data < pointer.data:
                if pointer.left == None:
                    pointer.left = Node(data)
                    break
                else:
                    pointer = pointer.left 
    def search(self, data):
        pointer = self.root
        process = []
        while True:
            if data > pointer.data:
                
                if pointer.right == None:
                    print('데이터가 없습니다.')
                    process = []       
                    break
                else:
                    process.append('R')
                    if pointer.right.data == data:
                        break
                    else:
                        pointer = pointer.right
            elif data < pointer.data:
                
                if pointer.left == None:
                    print('데이터가 없습니다.')
                    process = []       
                    break                
                else:
                    process.append('L')
                    if pointer.left.data == data:
                        break
                    else:
                        pointer = pointer.left
            else:
                return [0]
        return process                       

    def preorder(self, node):
        if node:
            print(node.data, end=' ')
            self.preorder(node.left)  #재귀끝나면 그 아래꺼 실행
            self.preorder(node.right)
    def inorder(self, node):
        if node:
            
            self.inorder(node.left)  #재귀끝나면 그 아래꺼 실행
            print(node.data, end=' ')
            self.inorder(node.right)
    def posterorder(self, node):
           if node:

               self.posterorder(node.left)  #재귀끝나면 그 아래꺼 실행
               self.posterorder(node.right)
               print(node.data, end=' ')
    def levelorder(self):
        que = deque()
        
        pointer = self.root #처음은 루트노드
        que.append(pointer)
        
        def reg(pointer):
            que.popleft()    
            print(pointer.data) #que에 나오면서 출력

            if pointer.left != None or pointer.right != None: #자식노드 큐에 삽입
              que.append(pointer.left)
              que.append(pointer.right)
            if que:   
              reg(que[0])

        reg(pointer)

 

 

 

 

위의 이진 탐색트리를 예시로 함

a = Bst(10)
a.add_(7)
a.add_(6)
a.add_(8)
a.add_(15)
a.add_(13)
a.add_(17)

 

a.preorder(a.root) #전위
a.inorder(a.root)  #중위
a.posterorder(a.root) #후위
a.levelorder()  #레벨

 

 

전위순회

중위순회

 

후위순회

레벨순회