[Algorithm] 이진 트리의 구현과 순회 알고리즘

 

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5/lecture/12349

알고리즘의 개요와 실습 환경 구축 - 인프런 | 학습 페이지

 

인프런 알고리즘 강의 20강에 대한 리뷰이다.

 

 

이진트리는 비선형 자료구조이고 데이터 탐색 속도 증진을 목적으로 한다.

트리는 배열이나 스택, 큐 등의 자료구조와 달리 데이터를 직관적으로 살펴보기 어렵기 때문에 별도의 순회 알고리즘이 필요하다.

 

 

Heap 정렬의 경우 완전 이진 트리를 전제로 한다.

불완전한 이진 트리의 경우 데이터 낭비를 피하기 위하여 포인터가 필요하다.

 

트리 순회 알고리즘은 트리에 저장된 모든 값을 살펴보고 싶을 때 사용한다.
이진 트리의 순회 방법 중 전위 순회(Pre-order Traversal), 중위 순회(In-order Traversal), 후위 순회(Post-order Traversal)가 있으며 이 순회 방법을 통틀어 깊이 우선 순회 방법(Depth First Traversal, DFS)라고 한다.
* 너비 우선 순회 방법(Breadth First Traversal)로는 레벨 순회가 있다.

참고: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html

Eunji Kim @ CAU - 파이썬을 사용한 이진 트리와 순회 알고리즘 구현 (2)

 

 

 

 

1. 전위 순회

 

출처: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html

 

자기 자신(부모 노드) -> 왼쪽 자식 -> 오른쪽 자식

 

 

 

2. 중위 순회

 

출처: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html

 

왼쪽 자식 -> 자기 자신 -> 오른쪽 자식

 

위 이미지를 가져온 블로그에 따르면 이진 탐색 트리를 정순회하면 정렬된 데이터를 얻을 수 있다는데 무슨 말인지 모르겠다.

 

 

 

위 이미지를 보면 이해할 것 같기도 하다.

 

 

3. 후위 순회

 

출처: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html

 

왼쪽 자식 -> 오른쪽 자식 -> 자기 자신

계산 관련 프로그램에서 많이 사용된다.

 

 

 

** C++

 

#include <iostream>

using namespace std;

int number = 15;

// 하나의 노드 정보를 선언합니다.
typedef struct node *treePointer; // node라는 구조체를 treePointer 라는 이름으로 이용하겠다.
typedef struct node {
	int data;
	treePointer leftChild, rightChild;
} node;

// 전위 순위 (Pre-order)
void preorder(treePointer ptr) {
	if(ptr) {
		cout << ptr->data << ' ';
		preorder(ptr->leftChild);
		preorder(ptr->rightChild);
	}
} 

// 중위 순위 (In-order)
void inorder(treePointer ptr) {
	if(ptr) {
		inorder(ptr->leftChild);
		cout << ptr->data << ' ';
		inorder(ptr->rightChild);
	}
}

// 후위 순위 (Post-order)
void postorder(treePointer ptr) {
	if(ptr) {
		postorder(ptr->leftChild);
		postorder(ptr->rightChild);
		cout << ptr->data << ' ';
	}
}

int main(void) {
	node nodes[number + 1];
	for (int i = 1; i <= number; i++) {
		nodes[i].data = i;
		nodes[i].leftChild = NULL;
		nodes[i].rightChild = NULL;		
	}
	for (int i = 1; i <= number; i++) {
		if (i % 2 == 0) {
			nodes[i / 2].leftChild = &nodes[i];
		} else {
			nodes[i / 2].rightChild = &nodes[i];
		}
	}
//	preorder(&nodes[1]);
//	inorder(&nodes[1]);
	postorder(&nodes[1]);
	return 0;
}

 

 

** Python

 

 

(시도중)

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


if __name__ == "__main__":
    nodes = [Node(i) for i in range(1, 16)]

 

 

어마어마한 코드를 발견해서 따라서 해봤는데 In-order 에서 자꾸 안된다.

일단 정렬된 트리라서 그런 것 같기도..

 

 

class Node(object):
    # 이진 탐색 트리를 구현하려면 Node 클래스 정의 필요
    # Node 클래스는 노드값(data) 과 좌/우 노드(left/right) 총 세개의 속성이 필요
    # 초기화할 때는 데이터 값만 주어지고 좌/우 노드 빈 상태
    def __init__(self, data):
        self.data = data
        self.left = self.right = None

class BinarySearchTree(object):
    def __init__(self):
        # 빈 트리
        self.root = None
    
    # 삽입: 새로운 원소 추가
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None
        
    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            """
            재귀 사용
            새로 추가할 원소의 값을 현재 노드의 값과
            비교하여 왼쪽/오른쪽 중 알맞은 위치로
            노드를 옮겨가며 삽입 위치 체크
            """
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node
        
    # 탐색: 원하는 값의 존재 유무 확인    
    def find(self, key):
        return self._find_value(self.root, key)
    
    # 재귀를 이용하여 대소관계 비교
    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)
    
    # 삭제
    def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted
        
    def _delete_value(self, node, key):
        if node is None:
            return node, False
            
        deleted = False
        if key == node.data:
            deleted = True
            if node.left and node.right:
                # replace the node to the leftmost of node.right
                """
                왼쪽 서브 트리와 오른쪽 서브 트리를
                각각 A, B라고 할 때, B에서 가장 왼쪽
                아래에 위치한 자손을 가져온다.
                이 원소는 A의 모든 원소들보다 크면서,
                B의 나머지 원소보다 작다
                """
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            elif node.left or node.right:
                node = node.left or node.right
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted
        
    def pre_order_traversal(self):
        def _pre_order_traversal(root):
            if root is None:
                pass
            else:
                print(root.data)
                _pre_order_traversal(root.left)
                _pre_order_traversal(root.right)
        _pre_order_traversal(self.root)
        # 자기자신(부모) -> 왼쪽 자식 -> 오른쪽 자식
    
    def in_order_traversal(self):
        def _in_order_traversal(root):
            if root is None:
                pass
            else:
                _in_order_traversal(root.left)
                print(root.data)
                _in_order_traversal(root.right)
        _in_order_traversal(self.root)
        # 왼쪽 자식 -> 자기 자신(부모) -> 오른쪽 자식
    
    def post_order_traversal(self):
        def _post_order_traversal(root):
            if root is None:
                pass
            else:
                _post_order_traversal(root.left)
                _post_order_traversal(root.right)
                print(root.data)
        _post_order_traversal(self.root)
        # 왼쪽 자식 -> 오른쪽 자식 -> 자기자신(부모)
    

def main() :
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11, 12, 13, 14, 15]
    
    bst = BinarySearchTree()
    for x in array:
        bst.insert(x)
    # depth first
    bst.pre_order_traversal()
    # bst.in_order_traversal()
    # bst.post_order_traversal()
    
if __name__ == "__main__":
    # execute only if run as a script
    main()

출처: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-2.html

 

 

위 버전을 그나마 축약 시킨 버전은 아래와 같다

근데 이것도 원하는 결과는 안 나온다.

 

class Node:
    # 이진 탐색 트리를 구현하려면 Node 클래스 정의 필요
    # Node 클래스는 노드값(data) 과 좌/우 노드(left/right) 총 세개의 속성이 필요
    # 초기화할 때는 데이터 값만 주어지고 좌/우 노드 빈 상태
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
    # insert
    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
    # Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print(self.data),
        if self.right:
            self.right.PrintTree()
    # Preorder traversal
    # Root -> Left ->Right
    # 자기자신(부모) -> 왼쪽 자식 -> 오른쪽 자식
    def PreorderTraversal(self, root):
        result = []
        if root:
            result.append(root.data)
            result = result + self.PreorderTraversal(root.left)
            result = result + self.PreorderTraversal(root.right)
        return result
    # Inorder traversal
    # Left -> Root -> Right
    # 왼쪽 자식 -> 자기 자신(부모) -> 오른쪽 자식
    def inorderTraversal(self, root):
        result = []
        if root:
            result = self.inorderTraversal(root.left)
            result.append(root.data)
            result = result + self.inorderTraversal(root.right)
        return result
    # Postorder traversal
    # Left ->Right -> Root
    # 왼쪽 자식 -> 오른쪽 자식 -> 자기자신(부모)
    def PostorderTraversal(self, root):
        result = []
        if root:
            result = self.PostorderTraversal(root.left)
            result = result + self.PostorderTraversal(root.right)
            result.append(root.data)
        return result

def main() :
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11, 12, 13, 14, 15]
    
    root = Node(1)
    root.insert(2)
    root.insert(3)
    root.insert(4)
    root.insert(5)
    root.insert(6)
    root.insert(7)
    root.insert(8)
    root.insert(9)
    root.insert(10)
    root.insert(11)
    root.insert(12)
    root.insert(13)
    root.insert(14)
    root.insert(15)
    # print(root.PreorderTraversal(root))
    print(root.inorderTraversal(root))
    # print(root.PostorderTraversal(root))
    
if __name__ == "__main__":
    # execute only if run as a script
    main()

 

 

이것도 중위 순위........

# 노드 만들기
#         A(val)
#        /      \
#   B(left)     C(right)
class Node:
    def __init__(self, item):
        self.val = item
        self.left = None
        self.right = None


# 이진트리 만들기
class BinaryTree:
    # 초기값 head는 None
    def __init__(self):
        self.head = Node(None)

        self.preorder_list=[]
        self.inorder_list=[]
        self.postorder_list=[]

    # 값 추가하기 head가 없을 경우
    def add(self, item):
        if self.head.val is None:
            self.head.val = item

        # head가 있으면 왼쪽배치 or 오른쪽배치
        else:
            self.__add_node(self.head, item)

    # head가 있는 경우
    def __add_node(self, cur, item):
        print('부모:', cur.val, '자식:', item)
        # head 값이 크면 왼쪽으로
        if cur.val >= item:
            if cur.left is not None:
                self.__add_node(cur.left, item)
            else:
                cur.left = Node(item)
        # head 값이 작으면 오른쪽으로
        else:
            if cur.right is not None:
                self.__add_node(cur.right, item)
            else:
                cur.right = Node(item)

    # 찾기!!
    def search(self, item):
        if self.head.val is None:
            return False
        else:
            return self.__search_node(self.head, item)

    def __search_node(self, cur, item):
        print(cur.val, item)
        if cur.val == item:
            return True
        else:
            if cur.val >= item:
                if cur.left is not None:
                    return self.__search_node(cur.left, item)
                else:
                    return False
            else:
                if cur.right is not None:
                    return self.__search_node(cur.right, item)
                else:
                    return False

    # 전위순회
    def preorder_traverse(self):
        if self.head is not None:
            self.__preorder(self.head)

    def __preorder(self, cur):
        self.preorder_list.append(cur.val)
        print(cur.val)
        if cur.left is not None:
            self.__preorder(cur.left)
        if cur.right is not None:
            self.__preorder(cur.right)

    # 중위순회
    def inorder_traverse(self):
        if self.head is not None:
            self.__inorder(self.head)

    def __inorder(self, cur):
        if cur.left is not None:
            self.__inorder(cur.left)

        self.inorder_list.append(cur.val)
        print(cur.val)

        if cur.right is not None:
            self.__inorder(cur.right)

    # 후위순회
    def postorder_traverse(self):
        if self.head is not None:
            self.__postorder(self.head)

    def __postorder(self, cur):
        if cur.left is not None:
            self.__postorder(cur.left)

        if cur.right is not None:
            self.__postorder(cur.right)

        self.postorder_list.append(cur.val)
        print(cur.val)


lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
bt = BinaryTree()
for num in lst:
    bt.add(num)


# print(bt.search(60))
# 전우
bt.preorder_traverse()
print(bt.preorder_list)
# 중위
bt.inorder_traverse()
print(bt.inorder_list)
# 후위
bt.postorder_traverse()
print(bt.postorder_list)

출처: https://deok2kim.tistory.com/110