[파이썬] DAY11 트리 코드 리뷰

계층적 연결구조라는 점에서 이중 연결리스트와는 다르다.

class Node:
    def __init__(self,item,left=None, right=None):
        self.item = item
        self.left = left
        self.right = right
        
class BinaryTree:
    def __init__(self): 
        self.root =None

    def preorder(self,n): 
        if n!=None: 
            print(str(n.item),'',end='') 
            if n.left:
                self.preorder(n.left)
            if n.right:
                self.preorder(n.right)
              
    def inorder(self,n): 
        if n!=None:
            if n.left:
                self.inorder(n.left)
            print(str(n.item),'',end='')
            if n.right:
                self.inorder(n.right)
            
    def postorder(self,n): 
        if n!=None:
            if n.left:
                self.postorder(n.left)
            if n.right:
                self.postorder(n.right)
            print(str(n.item),'',end='')
            
        
    def levelorder(self, root):  
        queue  = []         
        queue.append(root)
        while queue: 
            node = queue.pop(0)  
            print(str(node.item),'',end="") 
            if node.left:
                queue.append(node.left) 
            if node.right:
                queue.append(node.right)
            
    
    def height(self,root):  
        if root == None:
            return 0
        return max(self.height(root.left),self.height(root.right)) +1
    
t = BinaryTree()
n1 = Node(100)
n2 = Node(200)
n3 = Node(300)
n4 = Node(400)
n5 = Node(500)
n6 = Node(600)
#n7 = Node(700)
#n8 = Node(800)
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
#n3.right = n7
#n4.left = n8 
t.root = n1


print('\n전위순회:\t', end ="")
t.preorder(t.root)
print('\n중위순회:\t', end ="")
t.inorder(t.root)
print('\n후위순회:\t', end ="")
t.postorder(t.root)

print('\n레벨순회:\t', end ="")
t.levelorder(t.root)

print('트리높이=', t.height(t.root))

 

 

 

 

 

 

 

 

---

이진 탐색 트리 예제1

class Node:
    def __init__(self,key,value, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        
class BST:
    def __init__(self): # 트리 생성자
        self.root = None
    
    
    def get(self,k): # 탐색 연산  
        result = self.get_item(self.root,k)
    
        return result
    
    def get_item(self,n,k):
        
        if n== None:
            return

        if n.key == k:
            return n.value
            
        elif n.key > k:
            value = self.get_item(n.left,k)
    
        elif n.key < k:
            value = self.get_item(n.right,k)
            
            
        
            
        return value
        
    
    def put(self, key, value): # 삽입 연산)
        self.root = self.put_item(self.root,key,value)
        

    def put_item(self,n,key, value):
        
        if n == None:
            n = Node(key,value,left=None,right=None)
        
        elif n.key > key:
            n.left = self.put_item(n.left,key,value)
            
        elif n.key < key:
            n.right = self.put_item(n.right,key,value)
        
        elif n.key == key:
            n.value = value
            
        return n 


# 책의 내용 따라가 보면 
    def minn(self): # 최솟값 가진 노드 찾기.

        if self.root == None:
            return None
        
        return self.minimum(self.root)
    
    def minimum(self,n):
        if n.left == None:
            return n
        return self.minimum(n.left)


# 책보고 다시 해봄. 
    def delete_min(self): # 최솟값 삭제  
        if self.root == None:
            return None
        
        self.root = self.del_min(self.root)
        
    
    def del_min(self, n):
        if n.left == None:
            return n.right
        else:
            n.left = self.del_min(n.left)
        
        return n

        
# 책보고 다시 해봄.
    def delete(self,k): # 삭제 연산 
        self.root = self.del_node(self.root,k)
    
    def del_node(self,n,k):

        if n == None:
            return None

        if n.key == k:
        
            if n.left == None:
                return n.right
            if n.right == None:
                return n.left
            
            target = n
            n = self.minimum(target.right) #중위순회 다음타자.
            n.right =  self.del_min(target.right)
            n.left = target.left            

        elif n.key > k:
            n.left = self.del_node(n.left,k)
            
        elif n.key < k:
            n.right = self.del_node(n.right,k)
        
        
        return n
        
        
        
        
    
    
    # 전위순회 
    def pre_order(self,n):
        
        if n == None:
            return
        
        print(n.key," ", end="")
        self.pre_order(n.left)
        self.pre_order(n.right)
        
        
    # 중위순회 
    def inorder(self,n):
        
        if n == None:
            return
        self.inorder(n.left)
        print(n.key," ",end="")
        self.inorder(n.right)


bts = BST()
bts.put(500,'apple')
bts.put(600,'banana')
bts.put(200,'melon')
bts.put(100,'orange')
bts.put(400,'lime')
bts.put(250,'kiwi')
bts.put(150,'grape')
bts.put(800,'peach')
bts.put(700,'cherry')
bts.put(50,'pear')
print(bts.get(700))
bts.put(350,'lemon')
bts.put(10,'plum')

print('전위순회 \t',"", end="")
bts.pre_order(bts.root)
print(' ')
print('중위순회 \t',"", end="")
bts.inorder(bts.root)


result = bts.get(400)
print('\n', '탐색연산  key: 400, result: ', result)  

result2 = bts.minn()
print('\n 최솟값: ', result2.key)

bts.delete_min()
print('\n 최솟값 삭제연산 ', end ="")
bts.inorder(bts.root)

bts.delete(200)
print('\n삭제 연산 1 : ', end ="")
bts.inorder(bts.root)

bts.delete(700)
print('\n삭제 연산 2 : ', end ="")
bts.inorder(bts.root)

bts.delete(50)
print('\n삭제 연산 3 : ', end ="")
bts.inorder(bts.root)

---

 

 

 

이진 탐색 트리 예제2

class Node(object):
    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:
            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,dleted = self._delete_value(node.right, key)
      return node, deleted

array = [40, 4, 34, 45, 14, 55, 48, 13, 15, 49, 47,40]

bst = BinarySearchTree()
for x in array:
    bst.insert(x)
print(bst)

# Find
print(bst.find(15)) # True
print(bst.find(17)) # False

# Delete
print(bst.delete(55)) # True
print(bst.delete(14)) # True
print(bst.delete(11)) # False
print(bst.delete(55))