(Python/이진트리)이진트리(1)

size() - 노드의 수

depth() 트리의 깊이

traversal : 순회

 

Node 는 Data ,leftchild, rightchild 를 가진다.

 

순회 종류:

 

1.깊이 우선순회

• 중위 순회 : 가운데 자기자신 left > 자신 > right 

중위 순회

• 전위 순회 : 자기자신 먼저

전위 순회

 

• 후위 순회 : 자기자신이 맨 마지막

D에 입장에서 생각했을때  자기자신 D를 맨 마지막에 방문하고

그 다음 B에 left , right, 자신 순서니깐 D 다음에 B가 아닌 E 부터 방문한다.

 

1-1

depth 구현

class Node:

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


    def size(self):
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1

    def depth(self):
        l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        if(r > l):
            return r + 1
        else:
            return l + 1


class BinaryTree:

    def __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0



    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0


def solution(x):
    return 0

 

 

1-2 이진트리 전위순회 연산 구현

class Node:

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


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal

class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []



def solution(x):
    return 0

먼저 데이터를 넣고 왼쪽 부터 순회

 

1-3 후위순회 

 

class Node:

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


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal


    def postorder(self):
        traversal =[]
        if self.left:
            traversal += self.left.postorder()
        if self.right:
            traversal += self.right.postorder()
        traversal.append(self.data)
        return traversal



class BinaryTree:

    def __init__(self, r):
        self.root = r


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []


    def postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []



def solution(x):
    return 0

왼쪽부터 쭉 가고 오른쪽 그리고 자기자신