Python-이진 트리

트리는 가장자리로 연결된 노드를 나타냅니다. 비선형 데이터 구조입니다. 다음과 같은 속성이 있습니다.

한 노드는 루트 노드로 표시됩니다.
루트를 제외한 모든 노드는 하나의 상위 노드와 연결됩니다.
각 노드는 chid 노드의 arbiatry 번호를 가질 수 있습니다.

앞에서 설명한 os 노드 개념을 사용하여 파이썬에서 트리 데이터 구조를 만듭니다. 한 노드를 루트 노드로 지정한 다음 더 많은 노드를 자식 노드로 추가합니다. 다음은 루트 노드를 생성하는 프로그램입니다.

루트 생성

Node 클래스를 만들고 노드에 값을 할당하기 만하면됩니다. 이것은 루트 노드 만있는 트리가됩니다.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

트리에 삽입

트리에 삽입하기 위해 위에서 만든 동일한 노드 클래스를 사용하고 여기에 삽입 메서드를 추가합니다. insert 메서드는 노드의 값을 부모 노드와 비교하여 왼쪽 노드 또는 오른쪽 노드로 추가하기로 결정합니다. 마지막으로 PrintTree 메서드는 트리를 인쇄하는 데 사용됩니다.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        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()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

3 6 12 14

나무 횡단

트리는 각 노드를 방문 할 시퀀스를 결정하여 순회 할 수 있습니다. 명확하게 알 수 있듯이 노드에서 시작한 다음 왼쪽 하위 트리를 먼저 방문하고 다음으로 오른쪽 하위 트리를 방문 할 수 있습니다. 또는 오른쪽 하위 트리를 먼저 방문하고 그다음에 왼쪽 하위 트리를 방문 할 수도 있습니다. 따라서 이러한 트리 탐색 방법에는 다른 이름이 있습니다. 여기 트리 탐색 알고리즘을 구현하는 장에서 자세히 연구합니다. 트리 탐색 알고리즘