Binary Search Tree

Binary Search Tree

Traverse 방식

pre order traverse (depth-first traverse라고도함.)

• visit the root
• traverse the left subtree
• traverse the right subtree

사용처는 byte-stream으로 tree 정보를 다른 곳으로 전송 할 때 사용 한다.

in-order traverse (symmetric traverse)

• visit left
• visit parent
• visit right

순차적으로 데이터를 출력 할 때 사용 한다.

post order traverse

• visit left
• visit right
• visit root

노드를 지워야 할 때 사용한다.

구현 코드

생성한 트리의 모습은 아래와 같다.

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert(self, value):
        if value <= self.data:
            if self.left is None:
                self.left = Node(value)
            else:
                self.left.insert(value)
        elif value > self.data:
            if self.right is None:
                self.right = Node(value)
            else:
                self.right.insert(value)
        else:
            self.data = value

    def inOrder(self):
        if self.left is not None:
            self.left.inOrder()
        print(self.data)
        if self.right is not None:
            self.right.inOrder()

    def preOrder(self):
        print(self.data)
        if self.left is not None:
            self.left.preOrder()
        if self.right is not None:
            self.right.preOrder()

    def postOrder(self):
        if self.left is not None:
            self.left.postOrder()
        if self.right is not None:
            self.right.postOrder()
        print(self.data)

if __name__ == "__main__":
    char = None
    root = Node(4)
    root.insert(3)
    root.insert(6)
    root.insert(2)
    root.insert(1)
    root.insert(5)
    root.insert(7)
    root.insert(8)

    print("inOrder traversal:")
    root.inOrder()
    print("preOrder traversal:")
    root.preOrder()
    print("PostOrder traversal:")
    root.postOrder()

참고문헌

한글로 설명된 깔끔한 블로그
설명 잘 되어 있는 외국 사이트